数据太水了
可以做到nlogn的
评测详情编译成功 - 测试点1：通过该数据点。得分10，耗时 15 ms，内存 7692 kb。
- 测试点2：通过该数据点。得分10，耗时 0 ms，内存 7692 kb。
- 测试点3：通过该数据点。得分10，耗时 15 ms，内存 7692 kb。
- 测试点4：通过该数据点。得分10，耗时 0 ms，内存 7692 kb。
- 测试点5：通过该数据点。得分10，耗时 15 ms，内存 7770 kb。
- 测试点6：通过该数据点。得分10，耗时 15 ms，内存 7757 kb。
- 测试点7：通过该数据点。得分10，耗时 15 ms，内存 7802 kb。
- 测试点8：通过该数据点。得分10，耗时 15 ms，内存 7774 kb。
- 测试点9：通过该数据点。得分10，耗时 15 ms，内存 7774 kb。
- 测试点10：通过该数据点。得分10，耗时 15 ms，内存 7811 kb。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<vector> #include<set> #include<map> #include<string> #include<algorithm> #define FOR(i,a,b) for(i=(a);i<=(b);i++) #define ROF(i,a,b) for(i=(a);i>=(b);i--) #define pb push_back #define mp make_pair #define PR pair<int,int> #define N 100010 using namespace std; typedef long long LL; typedef long double LD; int stack[N],a[N],ans[N]; int n,C; struct node{int l,r;PR m;}; PR min(PR a,PR b) { if (a<b) return a; return b; } struct segtree { node tree[4*N]; void update(int x) {tree[x].m=min(tree[x<<1].m,tree[(x<<1)+1].m);} void build(int x,int L,int R) { tree[x].l=L;tree[x].r=R;int M=(L+R)>>1; if (L==R) {tree[x].m=mp(a[L],L);return;} build(x<<1,L,M);build((x<<1)+1,M+1,R); update(x); } PR query(int x,int L,int R) { if (tree[x].l==L&&tree[x].r==R) return tree[x].m; int M=(tree[x].l+tree[x].r)>>1; if (R<=M) return query(x<<1,L,R); if (L>M) return query((x<<1)+1,L,R); return min(query(x<<1,L,M),query((x<<1)+1,M+1,R)); } }Tree; int main() { ios::sync_with_stdio(false); scanf("%d %d",&n,&C); int i; FOR(i,1,n) scanf("%d",&a[i]); Tree.build(1,1,n); int c=C,top=0,len=0,j; i=1; while (len<n) { if ((!c)||(i>n)) { len++; ans[len]=stack[top]; top--;c=1;i++; continue; } PR Min=Tree.query(1,i,min(n,i+c-1)); while ((stack[top]<=Min.first)&&(top>0)) { len++;ans[len]=stack[top];top--;c++; Min=Tree.query(1,i,min(n,i+c-1)); } int p=Min.second; len++;ans[len]=Min.first; FOR(j,i,p-1) {top++;stack[top]=a[j];c--;} i=p+1; } FOR(i,1,len-1) printf("%d ",ans[i]); printf("%d\n",ans[len]); return 0; }
|