oj.uz

Submission #545043

# Submission time Handle Problem Language Result Execution time Memory
545043 2022-04-03T12:00:42 Z David_M Teams (IOI15_teams) C++14
100 / 100
 1482 ms 388244 KB 
//#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 21824 KB Output is correct
2 Correct 22 ms 21800 KB Output is correct
3 Correct 23 ms 21824 KB Output is correct
4 Correct 21 ms 21884 KB Output is correct
5 Correct 25 ms 21872 KB Output is correct
6 Correct 23 ms 22076 KB Output is correct
7 Correct 20 ms 21832 KB Output is correct
8 Correct 21 ms 21896 KB Output is correct
9 Correct 20 ms 21824 KB Output is correct
10 Correct 21 ms 21836 KB Output is correct
11 Correct 26 ms 21824 KB Output is correct
12 Correct 23 ms 21824 KB Output is correct
13 Correct 22 ms 21880 KB Output is correct
14 Correct 22 ms 21912 KB Output is correct
15 Correct 22 ms 21888 KB Output is correct
16 Correct 22 ms 21904 KB Output is correct
17 Correct 22 ms 21780 KB Output is correct
18 Correct 25 ms 21856 KB Output is correct
19 Correct 26 ms 21792 KB Output is correct
20 Correct 21 ms 21824 KB Output is correct
21 Correct 21 ms 21756 KB Output is correct
22 Correct 23 ms 21816 KB Output is correct
23 Correct 21 ms 21824 KB Output is correct
24 Correct 22 ms 21764 KB Output is correct
25 Correct 26 ms 21824 KB Output is correct
26 Correct 24 ms 21772 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 88924 KB Output is correct
2 Correct 145 ms 88900 KB Output is correct
3 Correct 169 ms 88996 KB Output is correct
4 Correct 152 ms 89684 KB Output is correct
5 Correct 108 ms 88932 KB Output is correct
6 Correct 115 ms 88888 KB Output is correct
7 Correct 113 ms 88956 KB Output is correct
8 Correct 106 ms 88900 KB Output is correct
9 Correct 153 ms 94184 KB Output is correct
10 Correct 142 ms 92200 KB Output is correct
11 Correct 120 ms 89008 KB Output is correct
12 Correct 114 ms 89056 KB Output is correct
13 Correct 117 ms 88912 KB Output is correct
14 Correct 128 ms 88920 KB Output is correct
15 Correct 138 ms 88904 KB Output is correct
16 Correct 138 ms 89024 KB Output is correct
17 Correct 113 ms 88996 KB Output is correct
18 Correct 115 ms 88928 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 88880 KB Output is correct
2 Correct 166 ms 88932 KB Output is correct
3 Correct 357 ms 96376 KB Output is correct
4 Correct 145 ms 89696 KB Output is correct
5 Correct 202 ms 88932 KB Output is correct
6 Correct 179 ms 88908 KB Output is correct
7 Correct 116 ms 88908 KB Output is correct
8 Correct 176 ms 88964 KB Output is correct
9 Correct 151 ms 93936 KB Output is correct
10 Correct 200 ms 94192 KB Output is correct
11 Correct 235 ms 94028 KB Output is correct
12 Correct 254 ms 94076 KB Output is correct
13 Correct 317 ms 94000 KB Output is correct
14 Correct 403 ms 95516 KB Output is correct
15 Correct 208 ms 88912 KB Output is correct
16 Correct 181 ms 88908 KB Output is correct
17 Correct 163 ms 89084 KB Output is correct
18 Correct 165 ms 89044 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 804 ms 364392 KB Output is correct
2 Correct 853 ms 364432 KB Output is correct
3 Correct 1385 ms 388244 KB Output is correct
4 Correct 788 ms 364460 KB Output is correct
5 Correct 664 ms 361672 KB Output is correct
6 Correct 620 ms 361728 KB Output is correct
7 Correct 469 ms 361740 KB Output is correct
8 Correct 630 ms 361696 KB Output is correct
9 Correct 687 ms 387428 KB Output is correct
10 Correct 718 ms 378808 KB Output is correct
11 Correct 840 ms 378748 KB Output is correct
12 Correct 901 ms 379620 KB Output is correct
13 Correct 1140 ms 381412 KB Output is correct
14 Correct 1482 ms 386052 KB Output is correct
15 Correct 782 ms 364160 KB Output is correct
16 Correct 773 ms 364412 KB Output is correct
17 Correct 585 ms 363608 KB Output is correct
18 Correct 586 ms 363592 KB Output is correct