Submission #377846

#	Time	Username	Problem	Language	Result	Execution time	Memory
377846		astoria	역사적 조사 (JOI14_historical)	C++14	40 / 100	4026 ms	130028 KiB

historic

#include "bits/stdc++.h"
using namespace std;

const int N=1e5+5,Q=1e5+5;
const int S = 600;
struct Query{
	int l,r,p,bk;
};
Query qr[Q];
int n,q,x[N];

struct node{
	int s,e,m; long long val;
	node *l, *r;
	node(int _s, int _e){
		s=_s; e=_e;
		m=(s+e)>>1;
		val = 0;
	}
	
	void create(){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int p, int v){
		if(s==e) val += (long long) v;
		else{
			if(l==NULL) create();
			if(p<=m) l->upd(p,v);
			else r->upd(p,v);
			
			val = max(l->val,r->val);
		}
	}
	
	long long qry(){
		return val;
	}
	
} *root;

bool comp(Query A, Query B){
	if(A.bk != B.bk) return A.bk < B.bk;
	return A.bk % 2 ? A.r > B.r : A.r < B.r;
}

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin>>n>>q;
	for(int i=1; i<=n; i++) cin>>x[i];
	for(int i=0; i<q; i++){
		cin>>qr[i].l>>qr[i].r;
		qr[i].p = i;
		qr[i].bk = qr[i].l / S;
	}
	sort(qr,qr+q,comp);
	
	root = new node(0,(int) 1e9+5);
	
	int mo_left = 1, mo_right = 0;
	
	long long ans[q];
	
	for(int i=0; i<q; i++){
		int left = qr[i].l, right = qr[i].r;
		while(mo_right < right){
			++mo_right;
			int t = x[mo_right];
			root->upd(t,t);
		}
		while(mo_left > left){
			--mo_left;
			int t = x[mo_left];
			root->upd(t,t);
		}
		while(mo_right > right){
			int t = x[mo_right];
			root->upd(t,-t);
			--mo_right;
		}
		while(mo_left < left){
			int t = x[mo_left];
			root->upd(t,-t);
			++mo_left;
		}
		ans[qr[i].p] = root->qry();
		//cout<<"HI"<<endl;
		//cout<<qr[i].l<<' '<<qr[i].r<<' '<<ans[qr[i].p]<<endl;
	}
	
	for(int i=0; i<q; i++) cout<<ans[i]<<'\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 0 / 60