oj.uz

Submission #232795

# Submission time Handle Problem Language Result Execution time Memory
232795 2020-05-18T07:06:36 Z anubhavdhar Sails (IOI07_sails) C++14
100 / 100
 280 ms 10616 KB 
#include<bits/stdc++.h>

#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i,n) for(i=0;i<(n);++i)
#define FORe(i,n) for(i=1;i<=(n);++i)
#define FORr(i,a,b) for(i=(a);i<(b);++i)
#define FORrev(i,n) for(i=(n);i>=0;--i)
#define ii pair<ll,ll>
#define vi vector<ll>
#define vii vector<ii>
#define ff first 
#define ss second
#define cd complex<double>
#define vcd vector<cd>
#define ldd long double
#define dbgLine cout<<"Line : "<<__LINE__<<'\n'
#define all(x) (x).begin(),(x).end()

using namespace std;

const short int __PRECISION = 10;

const ll MOD = 1e9+7;
const ll INF = 1e17 + 1101;
const ll LOGN = 17;
const ll MAXN = 1e5+5;
const ll ROOTN = 320;

const ldd PI = acos(-1);
const ldd EPS = 1e-7;

struct Segtree
{
	ll st[MAXN*4], lz[MAXN*4];

	inline void push(ll node, ll ss, ll se)
	{
		if(lz[node] == 0)
			return;
		if(ss != se)
		{
			lz[node*2+1] += lz[node];
			lz[node*2+2] += lz[node];
		}
		// cout<<"pushing ["<<ss<<','<<se<<"] "<<lz[node]<<'\n';
		st[node] += (se - ss + 1)*lz[node];
		lz[node] = 0;
	}

	void upd(ll node,ll ss, ll se, ll l, ll r, ll val)
	{
		push(node, ss, se);
		if(r < ss or l > se)	return;
		if(l <= ss and r >= se)
		{
			lz[node] += val;
			push(node,ss,se);
			return;
		}
		ll mid = (ss+se)/2;
		upd(node*2+1, ss, mid, l, r, val);
		upd(node*2+2, mid + 1, se, l, r, val);
		st[node] += st[node*2+1] + st[node*2+2];
		push(node, ss, se);
	}

	ll quer(ll node, ll ss, ll se,ll i)
	{
		push(node,ss,se);
		assert(!(i < ss or i > se));
		if(ss == se)
			return st[node];
		ll mid = (ss + se)/2;
		return ((i > mid) ? quer(node*2+2, mid + 1, se, i) : quer(node*2+1, ss, mid, i));
	}

	Segtree()
	{
		int i;
		FOR(i, 4* MAXN) 
			st[i] = lz[i] = 0;
	}

	inline void update(ll l, ll r, ll val)
	{
		if (l > r)return;
		upd(0,0,MAXN,l,r,val);
	}

	inline ll query(ll i)
	{
		return quer(0,0,MAXN,i);
	}
} S;

int main()
{
	/*
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	*/

	int N, i, j, k;
	cin>>N;
	pair<int,int> pole[N];
	FOR(i,N)
	{
		cin>>j>>k;
		pole[i] = mp(j,k);
	}
	sort(pole, pole + N);

	int top = 0;
	set<int> partitions;
	partitions.insert(0);
	// partitions.insert(99999999);

	S.update(0, 0, MAXN);

	FOR(i, N)
	{
		if (S.query(top) > 0 and top < pole[i].ff)	partitions.insert(top);
		top = pole[i].ff;
		if(pole[i].ss == 0) continue;
		set<int> :: iterator it = partitions.lower_bound(top - pole[i].ss);
		bool ok = it != partitions.end();
		int lst = top, a, b;
		if(ok) {lst = (*it); S.update(lst + 1, top, 1);}
		if(!ok or top - pole[i].ss != lst)
		{
			--it;
			S.update((*it) + 1,((*it) + pole[i].ss - top + lst), 1);
			partitions.insert((*it) + pole[i].ss - top + lst);
			a = S.query(*it), b = S.query(*it + 1);
			if(a == b)	partitions.erase(it);
		}
		if(ok)
		{
			a = S.query(lst), b = S.query(lst + 1);
			if(a == b)	partitions.erase(lst);
		}
		// cout<<"i = "<<i<<" pole : "<<pole[i].ff<<' '<<pole[i].ss<<"; top = "<<top<<endl;
		// FORe(j, top)	cout<<S.query(j)<<' ';
		// cout<<"\npartitions : ";
		// for(int x : partitions) cout<<x<<' ';
		// cout<<'\n';

	}
	ll ans = 0, tt;
	FORe(j, top)
	{
		tt = S.query(j);
		ans += (tt*(tt-1))/2;
	}
	cout<<ans;

		/*
		if(mn > 0)
			partitions.insert(-top);
		top = pole[i].ff;
		if(pole[i].ss == 0)	continue;
		set<int> :: iterator it = (partitions.lower_bound( -(top - pole[i].ss + 1)))
		int lst = -(*it);
		S.update(lst, top, 1);
		if (lst == 0)	continue;
		if(S.query(lst, lst) == S.query(lst - 1, lst - 1))
			partitions.erase(lst);
		it++;
		assert(it != S.end());
		int left = pole[i].ss - top + pole[i].ss - 1;
		if(left == 0)
			continue;
		S.update((*it), (*it) + left - 1, 1);
		partitions.insert((*it) + left)
		*/
	
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 8 ms 6528 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6656 KB Output is correct
2 Correct 8 ms 6528 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6784 KB Output is correct
2 Correct 9 ms 6528 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 6656 KB Output is correct
2 Correct 18 ms 6528 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 6784 KB Output is correct
2 Correct 71 ms 7144 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8572 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 7928 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 8312 KB Output is correct
2 Correct 203 ms 8884 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 10616 KB Output is correct
2 Correct 120 ms 7928 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 9316 KB Output is correct
2 Correct 178 ms 8440 KB Output is correct