Submission #134907

#	Time	Username	Problem	Language	Result	Execution time	Memory
134907		rajarshi_basu	Sails (IOI07_sails)	C++14	60 / 100	1085 ms	5784 KiB

sails

#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 (stderr)

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;
     ^~~

• 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: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10