| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 13708 |
2015-03-26T11:48:30 Z |
comet |
역사적 조사 (JOI14_historical) |
C++ |
|
4000 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)*root+a.e/root<(b.s/root)*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 |
3 ms |
9812 KB |
Output is correct |
| 3 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 4 |
Correct |
12 ms |
9812 KB |
Output is correct |
| 5 |
Correct |
27 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
46 ms |
9812 KB |
Output is correct |
| 7 |
Correct |
43 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 |
46 ms |
9812 KB |
Output is correct |
| 11 |
Correct |
49 ms |
9812 KB |
Output is correct |
| 12 |
Correct |
49 ms |
9812 KB |
Output is correct |
| 13 |
Correct |
44 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 |
49 ms |
9812 KB |
Output is correct |
| 17 |
Correct |
45 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 |
0 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 |
3 ms |
9812 KB |
Output is correct |
| 7 |
Correct |
2 ms |
9812 KB |
Output is correct |
| 8 |
Correct |
7 ms |
9944 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10200 KB |
Output is correct |
| 10 |
Correct |
20 ms |
10584 KB |
Output is correct |
| 11 |
Correct |
820 ms |
11352 KB |
Output is correct |
| 12 |
Correct |
46 ms |
11352 KB |
Output is correct |
| 13 |
Correct |
227 ms |
11352 KB |
Output is correct |
| 14 |
Correct |
527 ms |
11352 KB |
Output is correct |
| 15 |
Correct |
1323 ms |
11352 KB |
Output is correct |
| 16 |
Correct |
146 ms |
11352 KB |
Output is correct |
| 17 |
Correct |
89 ms |
11352 KB |
Output is correct |
| 18 |
Correct |
202 ms |
11352 KB |
Output is correct |
| 19 |
Correct |
195 ms |
11352 KB |
Output is correct |
| 20 |
Correct |
69 ms |
11352 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
106 ms |
9944 KB |
Output is correct |
| 2 |
Correct |
254 ms |
10200 KB |
Output is correct |
| 3 |
Correct |
440 ms |
10200 KB |
Output is correct |
| 4 |
Correct |
733 ms |
10584 KB |
Output is correct |
| 5 |
Correct |
995 ms |
10584 KB |
Output is correct |
| 6 |
Correct |
1192 ms |
10584 KB |
Output is correct |
| 7 |
Correct |
1566 ms |
11352 KB |
Output is correct |
| 8 |
Correct |
2189 ms |
11352 KB |
Output is correct |
| 9 |
Correct |
2830 ms |
11352 KB |
Output is correct |
| 10 |
Execution timed out |
4000 ms |
11352 KB |
Program timed out |
| 11 |
Halted |
0 ms |
0 KB |
- |
