Submission #120384

#	Time	Username	Problem	Language	Result	Execution time	Memory
120384		baluteshih	Sails (IOI07_sails)	C++14	100 / 100	215 ms	9212 KiB

sails

#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define F first
#define S second
#define MP make_pair
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cout << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

struct node
{
	ll key,lazy,sz,pri;
	node *l,*r;
	node(int k):key(k),lazy(0),sz(1),l(0),r(0),pri(rand()){}
	void down()
	{
		if(l) l->key+=lazy,l->lazy+=lazy;
		if(r) r->key+=lazy,r->lazy+=lazy;
		lazy=0;
	}
	void up()
	{
		sz=1;
		if(l) sz+=l->sz;
		if(r) sz+=r->sz;
	}
}*root;

ll ans;
pll arr[100005];

ll sz(node *o)
{
	return o?o->sz:0;
}

node *merge(node *a,node *b)
{
	if(!a||!b) return a?a:b;
	if(a->pri<b->pri)
		return a->down(),a->r=merge(a->r,b),a->up(),a;
	return b->down(),b->l=merge(a,b->l),b->up(),b;
}

void split(node *o,node *&a,node *&b,ll k)//split by key
{
	if(!o) return a=b=0,void();
	o->down();
	if(o->key<=k) a=o,split(o->r,a->r,b,k),a->up();
	else b=o,split(o->l,a,b->l,k),b->up();
}

void split2(node *o,node *&a,node *&b,ll k)//split by size
{
	if(!o) return a=b=0,void();
	o->down();
	if(sz(o->l)+1<=k) a=o,split2(o->r,a->r,b,k-sz(o->l)-1),a->up();
	else b=o,split2(o->l,a,b->l,k),b->up();
}

ll mxkey(node *o)
{
	while(o->r)
		o->down(),o=o->r;
	return o->key;
}

void dfs(node *o)
{
	o->down();
	ans+=o->key*(o->key-1)/2;
	if(o->l) dfs(o->l);
	//cout << o->key << " ";
	if(o->r) dfs(o->r);
}

int main()
{jizz
	ll n;
	srand(time(NULL));
	cin >> n;
	for(int i=0;i<n;++i)
		cin >> arr[i].F >> arr[i].S;
	sort(arr,arr+n);
	for(int i=0;i<n;++i)
	{
		//cout << i << " start\n";
		node *a,*b,*c,*d;
		while(sz(root)<arr[i].F)
			root=merge(new node(0),root);
		//cout << i << ": " << sz(root) << " part 1\n";
		split2(root,a,b,arr[i].S);
		//cout << i << ": " << sz(a) << " " << sz(b) << " part 2\n";
		ll mx=mxkey(a);
		//cout << i << ": " << mx << " part 3\n";
		a->key+=1,a->lazy+=1;
		split(a,a,c,mx),split(b,b,d,mx);
		root=merge(merge(a,b),merge(c,d));
		//cout << i << " done\n";
	}
	dfs(root);
	cout << ans << "\n";
}

Compilation message (stderr)

sails.cpp: In constructor 'node::node(int)':
sails.cpp:19:11: warning: 'node::r' will be initialized after [-Wreorder]
  node *l,*r;
           ^
sails.cpp:18:17: warning:   'll node::pri' [-Wreorder]
  ll key,lazy,sz,pri;
                 ^~~
sails.cpp:20:2: warning:   when initialized here [-Wreorder]
  node(int k):key(k),lazy(0),sz(1),l(0),r(0),pri(rand()){}
  ^~~~

• 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