Submission #13708

#	Time	Username	Problem	Language	Result	Execution time	Memory
13708		comet	역사적 조사 (JOI14_historical)	C++98	40 / 100	4000 ms	11352 KiB

historic

#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 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60