oj.uz

Submission #1067939

# Submission time Handle Problem Language Result Execution time Memory
1067939 2024-08-21T05:50:23 Z Muhammet Sails (IOI07_sails) C++17
100 / 100
 180 ms 14416 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4444 KB Output is correct
2 Correct 8 ms 11836 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5212 KB Output is correct
2 Correct 44 ms 5212 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 5712 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 10944 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 13652 KB Output is correct
2 Correct 122 ms 13904 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 14240 KB Output is correct
2 Correct 99 ms 13904 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 14416 KB Output is correct
2 Correct 122 ms 7504 KB Output is correct