| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 120384 |
2019-06-24T09:57:54 Z |
baluteshih |
Sails (IOI07_sails) |
C++14 |
|
215 ms |
9212 KB |
#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
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()){}
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
640 KB |
Output is correct |
| 2 |
Correct |
22 ms |
6620 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
2432 KB |
Output is correct |
| 2 |
Correct |
36 ms |
1368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
3068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
96 ms |
4828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
197 ms |
8664 KB |
Output is correct |
| 2 |
Correct |
183 ms |
8672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
164 ms |
9112 KB |
Output is correct |
| 2 |
Correct |
99 ms |
8200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
215 ms |
9212 KB |
Output is correct |
| 2 |
Correct |
126 ms |
4808 KB |
Output is correct |
