Submission #545043

#	Time	Username	Problem	Language	Result	Execution time	Memory
545043		David_M	Teams (IOI15_teams)	C++14	100 / 100	1482 ms	388244 KiB

teams

//#include "teams.h"
#include<bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
using namespace std;

const int NN=500000;
int f[NN+11];


struct Node{

    Node *left=nullptr, *right=nullptr;
    int cnt=0;

    Node(){}
    Node (Node *node) : left(node->left), right(node->right), cnt(node->cnt){}

    void extend(){
        if(!left){
            left = new Node();
            right = new Node();
        }
    }

    void add(int y, int l=0, int r=NN){
//        cout<<l<<" "<<r<<" "<<y<<endl;
        if(l+1==r){
            cnt+=1;
            return;
        }
        extend();
        int mid=l+r>>1;
        if(y<mid){
            left = new Node(left);
            left -> add(y, l, mid);
        }else{
            right = new Node(right);
            right -> add(y, mid, r);
        }
        cnt = left->cnt + right->cnt;
    }

    int get(int L, int R, int l=0, int r=NN){
//        cout<<"[L, R]: "<<L<<" "<<R<<endl;
//        cout<<"AAA"<<endl;
//        cout<<"[l, r, cnt]: "<<l<<" "<<r<<" "<<cnt<<endl;
        if(l>=R || r<=L)return 0;
        if(l>=L && r<=R){
//            cout<<endl<<"[L, R, l, r, cnt]: "<<L<<" "<<R<<" "<<l<<" "<<r<<" "<<cnt<<endl;
            return cnt;
        }
//        cout<<"![L, R]: "<<L<<" "<<R<<endl;
//        cout<<"!AAA"<<endl;
//        cout<<"![l, r, cnt]: "<<l<<" "<<r<<" "<<cnt<<endl;
        extend();
        int mid=l+r>>1;
        return left->get(L, R, l, mid) + right->get(L, R, mid, r);
    }

} node;

struct PST{

    int sz;
    vector<Node*> r;
    PST(){ sz=1; r.push_back(new Node()); }

    void add(int x, int y){
        while(sz<=x){
            r.push_back(new Node(r[sz-1]));
            sz++;
        }
//        cout<<r.size()<<" "<<sz<<endl;
        r[sz-1]->add(y);
//        cout<<"BBB"<<endl;
    }

    int get1(int xl, int xr, int y_min, int y_max){
//        cout<<endl<<"AAS"<<xr<<" "<<xl<<" "<<r[xr]->get(y_min, y_max)- r[max(0, xl-1)]->get(y_min, y_max)<<endl;
        return r[xr]->get(y_min, y_max) - r[max(0, xl-1)]->get(y_min, y_max);
    }

    int get2_1(Node *xl, Node *xr, int wcnt, int l=0, int r=NN){
//        cout<<"CCC "<<wcnt<<endl;
        if(l + 1 == r){
            if(wcnt > xr->cnt - xl->cnt){
                return 1000000000;
            }
            return r;
        }
        xl->extend();
        xr->extend();
        int cnt = xr->left->cnt - xl->left->cnt, mid=l+r>>1;
        return (cnt>=wcnt) ? get2_1(xl->left, xr->left, wcnt, l, mid)
                           : get2_1(xl->right, xr->right, wcnt - cnt, mid, r);

    }

    int get2(int xl, int xr, int y_min, int cnt){
//        cout<<"DDD "<<xl<<" "<<xr<<" "<<y_min<<" "<<get1(xl, xr, 0, y_min)<<endl;
        return get2_1(r[max(0, xl-1)], r[xr], cnt+get1(xl, xr, 0, y_min));
    }

};

PST *pst=new PST();

void init(int N, int A[], int B[]) {

    vector<array<int, 2>> v(N);

    for (int i=0; i<N; i++){
        v[i]={B[i], A[i]};
    }
//    cout<<N<<endl;

    sort(all(v));

    int o=1;

    int prev_y=0, new_y=0, Y=0;
    for (auto &[y,x] : v){

        if(y==prev_y){
            ++new_y;
            y=new_y;
        }else{
            prev_y=y;
            ++new_y;
            while(Y<y){
                Y++;
                f[Y]=new_y;
            }
            y=new_y;
        }
    }

//    for (auto &[y,x] : v){
//        y+=o;
//        if(f[y-o]==y-o)f[y-o]=y;
//        fr[y-o]=y;
//        o++;
//    }

    int X=f[Y]+1;
    while(Y<NN){
        Y++;
        f[Y]=X;
    }

//    cout<<"[f]: ";
//    for (int i=0; i<10; i++){
//        cout<<f[i]<<" ";
//    }
//    cout<<endl;

//    cout<<"AAA"<<endl;

    for (auto &[y,x]:v)swap(x,y);
    sort(all(v));

//    cout<<"[y_x]: ";
//    for (auto [x,y]:v){
//            cout<<x<<"_"<<y<<" ";
//    }
//    cout<<endl;

    for (auto [x,y] : v){
        pst->add(x,y);
    }
    while(pst->sz<NN-1){
        pst->r.push_back(new Node(pst->r[pst->sz-1]));
        pst->sz++;
    }

}

int can(int M, int K[]) {
//    cout<<M<<endl;

    sort(K, K+M);
    array<int, 3> s[M+5];
    int o=0;


    //        xl  xr y_min
    s[o++] = {0, 0, f[NN-1]};

    for (int i=0; i<M; i++){
        int k=K[i];
        int xl=s[o-1][1]+1, xr=k, y_min=f[k], y_max=s[o-1][2], cnt=k, c;

//        if(i && k==K[i-1]){
//            if(o==1){
//                return 0;
//            }
//            xl=s[o-1][0], xr=s[o-1][1], y_min=s[o-1][2], y_max=s[o-2][2];
//        }
//        cout<<"DDD"<<pst->get1(xl, xr, y_min, y_max)<<endl;
        while(o>1 && cnt && (c=pst->get1(xl, xr, y_min, y_max)) <= cnt){
//            cout<<"[k, xl, xr, y_min, y_max, cnt]: ";
//            cout<<k<<" "<<xl<<" "<<xr<<" "<<y_min<<" "<<y_max<<" "<<cnt<<endl;
//            cout<<"[c, o]: "<<c<<" "<<o<<endl;
            cnt-=c;
            o--;
            xl=s[o][0];
            y_min=max(y_min, y_max);
            y_max=s[o-1][2];
        }
//        cout<<k<<" "<<cnt<<" "<<xr<<" "<<xl<<endl;
        if(cnt){
//                cout<<"AAA"<<xr<<" "<<xl<<endl;
//            cout<<"[k, xl, xr, y_min, y_max, cnt]: ";
//            cout<<k<<" "<<xl<<" "<<xr<<" "<<y_min<<" "<<y_max<<" "<<cnt<<endl;

            y_min = pst->get2(xl, xr, y_min, cnt);


//            cout<<y_min<<endl;
            if(y_min>NN){
                return 0;
            }
        }
        s[o++]={xl, xr, y_min};
//        cout<<"AQA "<<s[o-1][2]<<endl;
    }
	return 1;
}

Compilation message (stderr)

teams.cpp: In member function 'void Node::add(int, int, int)':
teams.cpp:32:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid=l+r>>1;
      |                 ~^~
teams.cpp: In member function 'int Node::get(int, int, int, int)':
teams.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid=l+r>>1;
      |                 ~^~
teams.cpp: In member function 'int PST::get2_1(Node*, Node*, int, int, int)':
teams.cpp:83:59: warning: declaration of 'r' shadows a member of 'PST' [-Wshadow]
   83 |     int get2_1(Node *xl, Node *xr, int wcnt, int l=0, int r=NN){
      |                                                       ~~~~^~~~
teams.cpp:65:19: note: shadowed declaration is here
   65 |     vector<Node*> r;
      |                   ^
teams.cpp:93:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |         int cnt = xr->left->cnt - xl->left->cnt, mid=l+r>>1;
      |                                                      ~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:122:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  122 |     for (auto &[y,x] : v){
      |                ^
teams.cpp:159:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  159 |     for (auto &[y,x]:v)swap(x,y);
      |                ^
teams.cpp:168:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  168 |     for (auto [x,y] : v){
      |               ^
teams.cpp:119:9: warning: unused variable 'o' [-Wunused-variable]
  119 |     int o=1;
      |         ^

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23