| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13710 |
2015-03-26T11:55:12 Z |
comet |
역사적 조사 (JOI14_historical) |
C++ |
|
3335 ms |
11352 KB |
#include<cstdio>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
#define int long long
vector<int> sortx;
int N,Q,x[100010],lookup[100010],root,sz;
struct range{
int s,e,v;
range(){}
range(int s_,int e_):s(s_),e(e_){}
}z[100010];
bool cmp(range a,range b){return (a.s/root)*2*root+a.e/root<(b.s/root)*2*root+b.e/root;}
struct ans{
int ret,v;
ans(){}
ans(int ret_,int v_):ret(ret_),v(v_){}
}A[100010];
bool cmp2(ans a,ans b){return a.v<b.v;}
int tree[400010];
void push(int x,int add){
tree[x]+=add;
for(int i=x/2;i>0;i>>=1){
tree[i]=max(tree[i*2],tree[i*2+1]);
}
}
main(){
int t;
scanf("%lld%lld",&N,&Q);
root=300;
sz=1;
while(sz<N)sz<<=1;
for(int i=1;i<=N;i++)scanf("%lld",&x[i]);
for(int i=0;i<Q;i++)scanf("%lld%lld",&z[i].s,&z[i].e),z[i].v=i;
for(int i=1;i<=N;i++)sortx.push_back(x[i]);
sort(sortx.begin(),sortx.end());
sortx.erase(unique(sortx.begin(),sortx.end()),sortx.end());
for(int i=1;i<=N;i++){
t=x[i];
x[i]=lower_bound(sortx.begin(),sortx.end(),x[i])-sortx.begin();
lookup[x[i]]=t;
}
sort(z,z+Q,cmp);
int L,R;
L=z[0].s;
R=z[0].s-1;
for(int i=0;i<Q;i++){
if(R<z[i].e){for(int j=R+1;j<=z[i].e;j++)push(x[j]+sz,lookup[x[j]]);R=z[i].e;}
else if(R>z[i].e){for(int j=R;j>z[i].e;j--)push(x[j]+sz,-lookup[x[j]]);R=z[i].e;}
if(L<z[i].s){for(int j=L;j<z[i].s;j++)push(x[j]+sz,-lookup[x[j]]);L=z[i].s;}
else if(L>z[i].s){for(int j=L-1;j>=z[i].s;j--)push(x[j]+sz,lookup[x[j]]);L=z[i].s;}
A[i]=ans(tree[1],z[i].v);
}
sort(A,A+Q,cmp2);
for(int i=0;i<Q;i++)printf("%lld ",A[i].ret);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 4 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 5 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 7 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 8 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 9 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 10 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 11 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 12 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 13 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 14 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 15 |
Correct |
0 ms |
9812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 4 |
Correct |
10 ms |
9812 KB |
Output is correct |
| 5 |
Correct |
27 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
43 ms |
9812 KB |
Output is correct |
| 7 |
Correct |
45 ms |
9812 KB |
Output is correct |
| 8 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 9 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 10 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 11 |
Correct |
43 ms |
9812 KB |
Output is correct |
| 12 |
Correct |
48 ms |
9812 KB |
Output is correct |
| 13 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 14 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 15 |
Correct |
48 ms |
9812 KB |
Output is correct |
| 16 |
Correct |
45 ms |
9812 KB |
Output is correct |
| 17 |
Correct |
48 ms |
9812 KB |
Output is correct |
| 18 |
Correct |
47 ms |
9812 KB |
Output is correct |
| 19 |
Correct |
48 ms |
9812 KB |
Output is correct |
| 20 |
Correct |
48 ms |
9812 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
1 ms |
9812 KB |
Output is correct |
| 4 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 5 |
Correct |
8 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
0 ms |
9812 KB |
Output is correct |
| 7 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 8 |
Correct |
3 ms |
9944 KB |
Output is correct |
| 9 |
Correct |
7 ms |
10200 KB |
Output is correct |
| 10 |
Correct |
15 ms |
10584 KB |
Output is correct |
| 11 |
Correct |
826 ms |
11352 KB |
Output is correct |
| 12 |
Correct |
45 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
230 ms |
11352 KB |
Output is correct |
| 14 |
Correct |
524 ms |
11352 KB |
Output is correct |
| 15 |
Correct |
1314 ms |
11352 KB |
Output is correct |
| 16 |
Correct |
149 ms |
11352 KB |
Output is correct |
| 17 |
Correct |
83 ms |
11352 KB |
Output is correct |
| 18 |
Correct |
212 ms |
11352 KB |
Output is correct |
| 19 |
Correct |
186 ms |
11352 KB |
Output is correct |
| 20 |
Correct |
75 ms |
11352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
9944 KB |
Output is correct |
| 2 |
Correct |
256 ms |
10200 KB |
Output is correct |
| 3 |
Correct |
439 ms |
10200 KB |
Output is correct |
| 4 |
Correct |
731 ms |
10584 KB |
Output is correct |
| 5 |
Correct |
987 ms |
10584 KB |
Output is correct |
| 6 |
Correct |
1198 ms |
10584 KB |
Output is correct |
| 7 |
Correct |
1576 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
2182 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
2827 ms |
11352 KB |
Output is correct |
| 10 |
Correct |
3327 ms |
11352 KB |
Output is correct |
| 11 |
Correct |
3094 ms |
11352 KB |
Output is correct |
| 12 |
Correct |
2818 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
2781 ms |
11352 KB |
Output is correct |
| 14 |
Correct |
3210 ms |
11352 KB |
Output is correct |
| 15 |
Correct |
3292 ms |
11352 KB |
Output is correct |
| 16 |
Correct |
3250 ms |
11352 KB |
Output is correct |
| 17 |
Correct |
3222 ms |
11352 KB |
Output is correct |
| 18 |
Correct |
3241 ms |
11352 KB |
Output is correct |
| 19 |
Correct |
3193 ms |
11352 KB |
Output is correct |
| 20 |
Correct |
3197 ms |
11352 KB |
Output is correct |
| 21 |
Correct |
3178 ms |
11352 KB |
Output is correct |
| 22 |
Correct |
3175 ms |
11352 KB |
Output is correct |
| 23 |
Correct |
3141 ms |
11352 KB |
Output is correct |
| 24 |
Correct |
3148 ms |
11352 KB |
Output is correct |
| 25 |
Correct |
3335 ms |
11352 KB |
Output is correct |
