oj.uz

답안 #13708

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13708 2015-03-26T11:48:30 Z comet 역사적 조사 (JOI14_historical) C++
40 / 100
 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);
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 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

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 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 -