Submission #491062

#	Time	Username	Problem	Language	Result	Execution time	Memory
491062		Haruto810198	Triple Jump (JOI19_jumps)	C++17	100 / 100	2182 ms	202772 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = 2147483647;
const int LNF = INF*INF;
const int MOD = 1000000007;
const int mod = 998244353;
const double eps = 1e-12;

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")

const int MAX = 500010;

int n, q;
int arr[MAX];
int ql[MAX], qr[MAX];

vector<pii> pairs;

vector<vi> ev;
// modify : time, 2, suf. pos, val
// query  : time = L, 1, R, id

int res[MAX];

int 

#define V st[cidx]
#define LC st[cidx*2]
#define RC st[cidx*2+1]

struct Node{
    int sl, sr;
	int Max;
	int change;
	int tag;
	bool cantag;
};

Node st[4*MAX];

void build(int cidx, int cl, int cr){
    V.sl = cl;
    V.sr = cr;
	V.change = 0;
	V.tag = 0;
	V.cantag = 1;
    if(cl < cr){
        int mid = (cl + cr) / 2;
        build(cidx*2, cl, mid);
        build(cidx*2+1, mid+1, cr);
        V.Max = max(LC.Max, RC.Max);
    }
    else{
        V.Max = arr[cl];
    }
}
 
void push(int cidx){
	if(V.tag == 0) return;
	V.Max += V.tag;
	assert(V.cantag == 1);
	V.change += V.tag;
	if(V.sl < V.sr){
		LC.tag += V.tag;
		RC.tag += V.tag;
	}
	V.tag = 0;
}
 
void pull(int cidx){
    push(cidx);
    if(V.sl < V.sr){
        push(cidx*2);
        push(cidx*2+1);
		V.Max = max(LC.Max, RC.Max);
		V.change = min(LC.change, RC.change);
	 	if(LC.change == RC.change and LC.cantag and RC.cantag) V.cantag = 1;
		else V.cantag = 0;
    }
}

void modify(int cidx, int ml, int mr, int val){
    if(mr < V.sl or V.sr < ml) return;
    
	pull(cidx);
	if(ml <= V.sl and V.sr <= mr){
        if(V.change < val and V.cantag){
			V.tag += val - V.change;
			return;
		}
		else if(val <= V.change){
			return;
		}
		else{
			modify(cidx*2, ml, mr, val);
    		modify(cidx*2+1, ml, mr, val);
   			pull(cidx);
		}
	}
	else{
		modify(cidx*2, ml, mr, val);
    	modify(cidx*2+1, ml, mr, val);
   	 	pull(cidx);
	}
}
 
int query(int cidx, int ql, int qr){
    if(qr < V.sl or V.sr < ql) return -INF;
    pull(cidx);
    if(ql <= V.sl and V.sr <= qr) return V.Max;
    return max( query(cidx*2, ql, qr) , query(cidx*2 + 1, ql, qr) );
}

void debug(){
	/*
	cerr<<"st : "<<endl;
	FOR(cidx, 1, 4*n, 1){
		if(V.sl == 0) continue;
		cerr<<"["<<V.sl<<", "<<V.sr<<"] ";
		cerr<<"change = "<<V.change<<", tag = "<<V.tag<<endl;
	}
	cerr<<endl;
	*/
}

signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	cin>>n;
	FOR(i, 1, n, 1){
		cin>>arr[i];
	}

	cin>>q;
	FOR(i, 1, q, 1){
		cin>>ql[i]>>qr[i];
	}
	
	vi mq;
	mq.pb(n);
	for(int i = n-1; i >= 1; i--){
		while(!mq.empty() and arr[mq.back()] < arr[i]){
			pairs.eb(i, mq.back());
			mq.pop_back();
		}

		if(!mq.empty()) pairs.eb(i, mq.back());
		mq.pb(i);
	}
	/*	
	cerr<<"pairs : "<<endl;
	for(pii p : pairs){
		cerr<<"("<<p.F<<", "<<p.S<<") "<<endl;
	}
	cerr<<endl;
	*/
	for(pii p : pairs){
		if(2 * p.S - p.F > n) continue;
		ev.pb({p.F, 2, 2 * p.S - p.F, arr[p.F] + arr[p.S]});
	}
	
	FOR(i, 1, q, 1){
		ev.pb({ql[i], 1, qr[i], i});
	}
	
	sort(ev.begin(), ev.end());
	reverse(ev.begin(), ev.end());
	
	build(1, 1, n);
	
	for(vi E : ev){
		int type = E[1];
		if(type == 2){ // modify
			int L = E[2];
			int val = E[3];
			modify(1, L, n, val);
			//cerr<<"modify ["<<L<<", "<<n<<"] val = "<<val<<endl;
			//debug();
		}
		else if(type == 1){ // query
			int L = E[0];
			int R = E[2];
			int id = E[3];
			res[id] = query(1, L, R);
			//cerr<<"query ["<<L<<", "<<R<<"] = "<<res[id]<<endl;
		}
	}

	FOR(i, 1, q, 1){
		cout<<res[i]<<'\n';
	}
	
	return 0;
	
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54