#include <bits/stdc++.h>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define ff first
#define ss second
#define vv vector
#define pb push_back
using namespace std;
/////////////////////////////////////////////////////////
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
uniform_int_distribution<int> uid(1,1<<30);
inline int getrandom(){
return uid(rng);
}
/////////////////////////////////////////////////////////
const int MAXN = 1e5 + 10;
struct Treap{
struct Node{
Node* left,*right;
int val;
int prior;
int lzp;
int sz;
Node(int v,Node *l = NULL,Node *r = NULL){
val = v;
left = l;
right = r;
lzp = 0;
sz = 1;
prior = getrandom();
if(l != NULL)sz += l->sz;
if(r != NULL)sz += r->sz;
}
};
Node* head = NULL;
Treap(){
head = NULL;
}
inline void reform(Node* node){
if(node==NULL)return;
node->sz = 1;
if(node->left != NULL)node->sz += node->left->sz;
if(node->right != NULL)node->sz += node->right->sz;
}
inline void pushdown(Node* node){
if(node==NULL)return;
if(node->left != NULL){
node->left->val += node->lzp;
node->left->lzp += node->lzp;
}
if(node->right != NULL){
node->right->val += node->lzp;
node->right->lzp += node->lzp;
}
node->lzp = 0;
}
int getValue(Node* node,int togo){
pushdown(node);
reform(node);
int lft = node->left == NULL? 0 : node->left->sz;
int rgt = node->right == NULL ? 0 : node->right->sz;
if(togo == lft + 1){
return node->val;
}else{
if(lft >= togo){
return getValue(node->left,togo);
}else{
return getValue(node->right,togo - lft - 1);
}
}
}
void split(Node* currnode,Node*& L,Node*& R,int val){
if(currnode == NULL){
L = NULL;
R = NULL;
return;
}
//cout <<"PRINTING THIS : " << currnode->val << endl;
pushdown(currnode);
//cout << "VALUE PUSHED " << endl;
if(val > currnode->val){
L = currnode;
split(currnode->right,L->right,R,val);
}else{
R = currnode;
split(currnode->left,L,R->left,val);
}
reform(currnode);
}
void merge(Node* left,Node* right,Node*& node){
if(left == NULL and right == NULL){
node = NULL;
}else if(left == NULL){
node = right;
}else if(right == NULL){
node = left;
}else{
pushdown(left);
pushdown(right);
if(left->prior > right->prior){
node = left;
merge(left->right,right,node->right);
}else{
node = right;
merge(left,right->left,node->left);
}
}
reform(node);
}
void updateSuffix(Node* node,int suf,int updv){
pushdown(node);
reform(node);
if(node == NULL or suf == 0)return;
int lft = node->left == NULL?0:node->left->sz;
int rgt = node->right == NULL?0:node->right->sz;
if(node->sz - lft <= suf){
// this node needs to be updated as well
node->val += updv;
}
if(suf == node->sz){
node->lzp += updv;
return;
}
updateSuffix(node->left,suf - 1 - rgt,updv);
updateSuffix(node->right,min(suf,rgt),updv);
}
void insert(){
Node* node = new Node(0);
//cout << "CH" << endl;
merge(node,head,head);
//cout << node << endl;
}
void markPref(int x){
//cout << "booo" << endl;
int val = getValue(head,x);
Node* lft = NULL,*mid = NULL,*rgt = NULL;
//cout << "HEHE" << endl;
split(head,lft,rgt,val+1);
//cout << "SPLITTING 1 DONE" << endl;
split(lft,lft,mid,val);
//cout << "TWO SPLITTINGS DONE" << endl;
if(mid != NULL){
// stuff is there to break and update
int lftover = x - (lft == NULL?0:lft->sz);
if(lftover > 0)
updateSuffix(mid,lftover,1);
}
if(lft != NULL){
lft->val++;
lft->lzp++;
}
merge(lft,mid,lft);
merge(lft,rgt,head);
}
void traverse(Node* node,vi& v){
if(node == NULL)return;
pushdown(node);
v.pb(node->val);
traverse(node->left,v);
traverse(node->right,v);
}
} treap;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;cin >> n;
vv<ii> all;
FOR(i,n){
int a,b;
cin >> a >> b;
all.pb({a,b});
}
sort(all.begin(),all.end());
int lst = 0 ;
for(auto e : all){
//cout << e.ff << endl;
while(lst < e.ff){
//cout << "bnubu" << endl;
treap.insert();
lst++;
// cout << lst << endl;
}
//cout << "G" << endl;
treap.markPref(e.ss);
}
vi x;
treap.traverse(treap.head,x);
sort(x.begin(),x.end());
ll cost = 0;
lst = -1;
ll cnt = 0;
for(auto e:x){
//cout << "FINAL VALUIE : : : : : " << e<< endl;
cost += ((ll)(e))*(e-1)/2;
}
cout << cost << endl;
return 0;
}
Compilation message
sails.cpp: In member function 'int Treap::getValue(Treap::Node*, int)':
sails.cpp:73:13: warning: unused variable 'rgt' [-Wunused-variable]
int rgt = node->right == NULL ? 0 : node->right->sz;
^~~
sails.cpp: In function 'int main()':
sails.cpp:214:5: warning: unused variable 'cnt' [-Wunused-variable]
ll cnt = 0;
^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
632 KB |
Output is correct |
| 2 |
Correct |
547 ms |
5784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
912 ms |
2104 KB |
Output is correct |
| 2 |
Correct |
170 ms |
1028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
2296 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
1932 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
5228 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1085 ms |
4232 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1076 ms |
2080 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
