Submission #1067939

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067939		Muhammet	Sails (IOI07_sails)	C++17	100 / 100	180 ms	14416 KiB

sails

#include <bits/stdc++.h>

using namespace std;

#define N 200005
#define ff first
#define ss second
#define int long long

int n, sti[N*8], sta[N*8], lz[N*8], ansr, ansl, ans = 0, x1;

bool tr;

pair <int,int> a[N];

void f(int nd, bool t){
	sti[nd] += lz[nd];
	sta[nd] += lz[nd];
	if(t == 0){
		lz[nd*2] += lz[nd];
		lz[nd*2+1] += lz[nd];
	}
	lz[nd] = 0;
}

pair<int,int> fnd(int nd, int l, int r, int ind){
	f(nd,(l==r));
	if((r < ind) or (l > ind)) return {sti[nd],sta[nd]};
	if(l == r){
		x1 = sta[nd];
		return {sti[nd],sta[nd]};
	}
	int md = (l + r) / 2;
	pair <int,int> a = fnd(nd*2,l,md,ind), b = fnd(nd*2+1,md+1,r,ind);
	sti[nd] = min(a.ff,b.ff);
	sta[nd] = max(a.ss,b.ss);
	return {sti[nd],sta[nd]};
}

pair<int,int> fndmax(int nd, int l, int r, int x){
	f(nd,(l==r));
	if(sti[nd] > x or tr == 1) return {sti[nd],sta[nd]};
	if(l == r){
		if(tr == 0){
			tr = 1;
			ansr = r;
		}
		return {sti[nd],sta[nd]};
	}
	int md = (l + r) / 2;
	pair <int,int> b = fndmax(nd*2+1,md+1,r,x), a = fndmax(nd*2,l,md,x);
	sti[nd] = min(a.ff,b.ff);
	sta[nd] = max(a.ss,b.ss);
	return {sti[nd],sta[nd]};
}

pair<int,int> fndmin(int nd, int l, int r, int x){
	f(nd,(l==r));
	if(sta[nd] < x or tr == 1) return {sti[nd],sta[nd]};
	if(l == r){
		if(tr == 0){
			tr = 1;
			ansl = l;
		}
		return {sti[nd],sta[nd]};
	}
	int md = (l + r) / 2;
	pair <int,int> a = fndmin(nd*2,l,md,x), b = fndmin(nd*2+1,md+1,r,x);
	sti[nd] = min(a.ff,b.ff);
	sta[nd] = max(a.ss,b.ss);
	return {sti[nd],sta[nd]};
}

pair<int,int> upd(int nd, int l, int r, int x, int y){
	f(nd,(l==r));
	if((r < x) or (l > y)) return {sti[nd],sta[nd]};
	if(l >= x and r <= y){
		lz[nd]++;
		f(nd,(l==r));
		return {sti[nd],sta[nd]};
	}
	int md = (l + r) / 2;
	pair <int,int> a = upd(nd*2,l,md,x,y), b = upd(nd*2+1,md+1,r,x,y);
	sti[nd] = min(a.ff,b.ff);
	sta[nd] = max(a.ss,b.ss);
	return {sti[nd],sta[nd]};
}

int f1(int x){
	return (x*(x-1))/2;
}

void dfs(int nd, int l, int r){
	f(nd,(l==r));
	if(l == r){
		ans += f1(sta[nd]);
		return;
	}
	int md = (l + r) / 2;
	dfs(nd*2,l,md);
	dfs(nd*2+1,md+1,r);
}

signed main(){
    cin >> n;
    vector <pair<int,int>> a(n);
    for(int i = 0; i < n; i++){
        cin >> a[i].ff >> a[i].ss;
    }
    sort(a.begin(), a.end());
    int H = a[n-1].ff;
    for(int i = 0; i < n; i++){
    	auto [h,k] = a[i];
    	int ind = (H-h+1);
    	fnd(1,1,H,ind+k-1);
    	int x = x1;
    	tr = 0;
    	fndmax(1,1,H,x);
    	tr = 0;
    	fndmin(1,1,H,x);
    	if(ind <= ansl-1){
    		upd(1,1,H,ind,ansl-1);
    		k -= (ansl-ind);
    	}
    	upd(1,1,H,ansr-k+1,ansr);
    }
    ans = 0;
    dfs(1,1,H);

    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10