Submission #1212273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212273		XCAC197	Teams (IOI15_teams)	C++20	0 / 100	4094 ms	69864 KiB

teams

#include "teams.h"
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <assert.h>
#define ll long long
using namespace std;

int N;
pair<int,int> ivs [500000];


int cNod = 5;
//roots[i] = all the rs after l
int roots [500000];
int val [5000000];
int lc [5000000];
int rc [5000000];

int nnod(){
    cNod++;
    return cNod;
}

int build(int cur, int l, int r){
    if(l == r){
        return cur;
    }else{
        lc[cur] = nnod();
        rc[cur] = nnod();
        build(lc[cur], l, (l+r)/2);
        build(rc[cur], (l+r)/2+1, r);
        return cur;
    }
}

int change(int cur, int l, int r, int x){
    if(l <= x && x <= r){
        int ncur = nnod();
        val[ncur] = val[cur]+1;
        if(l != r){
            lc[ncur] = change(lc[cur], l, (l+r)/2, x);
            rc[ncur] = change(rc[cur], (l+r)/2+1, r, x);
        }
        return ncur;
    }else{
        return cur;
    }
}

int query(int cur, int l, int r, int fl, int fr){
    if(fl > fr){
        return 0;
    }
    if(fl <= l && r <= fr){
        return val[cur];
    }else if(fr < l || r < fl){
        return 0;
    }else{
        return query(lc[cur], l, (l+r)/2, fl, fr) + query(rc[cur], (l+r)/2+1, r, fl, fr);
    }
} 


void init(int N_, int A_[], int B_[]) {
    N = N_;
    for(int i = 0; i < N; i++){
        ivs[i] = make_pair(A_[i], B_[i]);
    }
    sort(ivs, ivs+N);
    roots[0] = build(nnod(), 1, N);
    int c = 0;
    for(int i = 1; i <= N; i++){
        int croot = roots[i-1];
        while(c != N && i == ivs[c].first){
        //    cout << "!" << i << " " <<  ivs[c].first << " " << ivs[c].second << endl;
            croot = change(croot, 1, N, ivs[c].second);
            c++;
        }
        roots[i] = croot;
    }
    cerr << "INIT DONE!" << endl;
}

int can(int M, int K[]) {
    sort(K, K+M);
    int su = 0;
    for(int i = 0; i < M; i++){
        su += K[i];
    }
    if(su > N){
        return 0;
    }else{
        if(M <= 500){
          //  cerr << "PROCESSING" << endl;
            //M^2 log
            int cnt [M][M];
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    cnt[i][j] = 0;
                }
            }
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    if(j == M-1){
                        cnt[i][j] = query(roots[K[i]], 1, N, K[j], N);
                    }else{
                        cnt[i][j] = query(roots[K[i]], 1, N, K[j], K[j+1]-1);
                    }
                }
            }
           // cerr << "CNT INIT" << endl;
            for(int i = M-1; i >= 1; i--){
                for(int j = i; j < M; j++){
                    cnt[i][j] = cnt[i][j] - cnt[i-1][j];
                }
            }
            int cnt2 [M][M];
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    cnt2[i][j] = 0;
                }
            }
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    for(int k = j; k < M; k++){
                        int lb1 = 1;
                        int rb1 = K[j];
                        if(j != 0){
                            lb1 = K[j-1] + 1;
                        }
                        int lb2 = K[k];
                        int rb2 = N;
                        if(k != M-1){
                            rb2 = K[k+1] - 1;
                        }
                      //  cout << lb1 << " " << rb1 << " " << lb2 << " " << rb2 << endl;
                        if(lb1 <= ivs[i].first && ivs[i].first <= rb1 && lb2 <= ivs[i].second && ivs[i].second <= rb2){
                            cnt2[j][k]++;
                        }
                    }
                }
            }
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    cerr << cnt[i][j] << " ";
                }
                cerr << endl;
            }
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    cerr << cnt2[i][j] << " ";
                }
                cerr << endl;
            }
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    assert(cnt2[i][j] == cnt[i][j]);
                }
            }
           /* for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    cerr << cnt[i][j] << " ";
                }
                cerr << endl;
            }
            cerr << endl;*/
            //left endpoint, right endpoint
            priority_queue <pair<int,int>, vector<pair<int,int>>, greater <pair<int,int>>> pq;
            for(int i = 0; i < M; i++){
                for(int j = i; j < M; j++){
                    if(cnt[i][j] > 0){
                        pq.push(make_pair(j, i));
                    }
                }
                int c = K[i];
                while(!pq.empty()){
                    int r = pq.top().first;
                    int l = pq.top().second;
                    if(cnt[l][r] <= c){
                        c -= cnt[l][r];
                        cnt[l][r] = 0;
                        pq.pop();
                    }else{
                        cnt[l][r] -= c;
                        c = 0;
                        break;
                    }
                }
                if(c > 0){
                    return 0;
                }
            }
        }else{
            //N+M log 
            //do a manual scan
            priority_queue <int, vector<int>, greater <int>> pq;
            int cptr = 0;
            for(int i = 0; i < M; i++){
                while(cptr < N && ivs[cptr].first <= K[i]){
                    pq.push(ivs[cptr].second);
                    cptr++;
                }
                //remove not useful students
                while(!pq.empty() && (pq.top()) < K[i]){
                    pq.pop();
                }
                if((int)(pq.size()) < K[i]){
                    return 0;
                }else{
                    for(int j = 0; j < K[i]; j++){
                        pq.pop();
                    }
                }
            }
        }
        return 1;
    }
}

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