Submission #545026

#	Time	Username	Problem	Language	Result	Execution time	Memory
545026		David_M	Teams (IOI15_teams)	C++14	21 / 100	953 ms	524288 KiB

teams

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

const int NN=1000000;
int fl[NN+11], fr[NN+11];


struct Node{

    Node *left=nullptr, *right=nullptr;
    int l, r, cnt;

    Node(){}
    Node (int l, int r) : l(l), r(r), cnt(0){}
    Node (Node *node) : left(node->left), right(node->right), l(node->l), r(node->r), cnt(node->cnt){}

    void extend(){
        if(!left){
            int mid=l+r>>1;
            left = new Node(l, mid);
            right = new Node(mid, r);
        }
    }

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

    int get(int L, int R){
//        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();
        return left->get(L, R) + right->get(L, R);
    }

} node;

struct PST{

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

    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){
//        cout<<"CCC "<<wcnt<<endl;
        if(xl->l + 1 == xl->r){
            if(wcnt > xr->cnt - xl->cnt){
                return 1000000000;
            }
            return xl->r;
        }
        xl->extend();
        xr->extend();
        int cnt = xr->left->cnt - xl->left->cnt;
        return (cnt>=wcnt) ? get2_1(xl->left, xr->left, wcnt)
                           : get2_1(xl->right, xr->right, wcnt - cnt);

    }

    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<NN; i++){
        fl[i]=fr[i]=i;
    }


    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;
    for (auto &[y,x] : v){

        if(y==prev_y){
            ++new_y;
            fr[y]=new_y;
            y=new_y;
        }else{
            prev_y=y;
            if(y>new_y){new_y=y;continue;}
            ++new_y;
            fl[y]=fr[y]=new_y;
            y=new_y;
        }

    }

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


    for (int i=1; i<NN; i++){
        fl[i]=max(fl[i], fr[i-1]+1);
        fr[i]=max(fr[i], fr[i-1]+1);
    }

//    cout<<"[f]: ";
//    for (int i=0; i<10; i++){
//        cout<<fl[i]<<"_"<<fr[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, fl[NN-1]};

    for (int i=0; i<M; i++){
        int k=K[i];
        int xl=s[o-1][1]+1, xr=k, y_min=fl[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 constructor 'Node::Node(int, int)':
teams.cpp:16:22: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |                  ~~~~^
teams.cpp:13:12: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |            ^
teams.cpp:16:15: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |           ~~~~^
teams.cpp:13:9: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |         ^
teams.cpp: In constructor 'Node::Node(int, int)':
teams.cpp:16:22: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |                  ~~~~^
teams.cpp:13:12: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |            ^
teams.cpp:16:15: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |           ~~~~^
teams.cpp:13:9: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |         ^
teams.cpp: In constructor 'Node::Node(int, int)':
teams.cpp:16:22: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |                  ~~~~^
teams.cpp:13:12: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |            ^
teams.cpp:16:15: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
   16 |     Node (int l, int r) : l(l), r(r), cnt(0){}
      |           ~~~~^
teams.cpp:13:9: note: shadowed declaration is here
   13 |     int l, r, cnt;
      |         ^
teams.cpp: In member function 'void Node::extend()':
teams.cpp:21:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |             int mid=l+r>>1;
      |                     ~^~
teams.cpp: In member function 'void Node::add(int)':
teams.cpp:34:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |         if(y<(l+r>>1)){
      |               ~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:126:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  126 |     for (auto &[y,x] : v){
      |                ^
teams.cpp:163:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |     for (auto &[y,x]:v)swap(x,y);
      |                ^
teams.cpp:172:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  172 |     for (auto [x,y] : v){
      |               ^
teams.cpp:123:9: warning: unused variable 'o' [-Wunused-variable]
  123 |     int o=1;
      |         ^

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