oj.uz

Submission #384117

# Submission time Handle Problem Language Result Execution time Memory
384117 2021-03-31T13:30:45 Z doowey Teams (IOI15_teams) C++14
100 / 100
 3507 ms 142940 KB 
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)5e5 + 100;
const int T = (int)1e7 + 100;

struct node{
    int val;
    int lef;
    int rig;
};

int cur;
node V[T];

int n;
vector<pii> segm;
vector<pii> segt;

int upd(int node, int cl, int cr, int id, int vv){
    int cid = cur;
    V[cid].lef = -1;
    V[cid].rig = -1;
    if(node == -1)
        V[cid].val = 0;
    else{
        V[cid].val = V[node].val;
        V[cid].lef = V[node].lef;
        V[cid].rig = V[node].rig;
    }
    V[cid].val += vv;
    cur ++ ;
    if(cl == cr) return cid;
    int mid = (cl + cr) / 2;
    if(id <= mid){
        int go = V[cid].lef;
        V[cid].lef = upd(go, cl, mid, id, vv);
    }
    else{
        int go = V[cid].rig;
        V[cid].rig = upd(go, mid + 1, cr, id, vv);
    }
    return cid;
}

int get(int node, int cl, int cr, int tl, int tr){
    if(cr < tl || cl > tr) return 0;
    if(node == -1) return 0;
    if(cl >= tl && cr <= tr){
        return V[node].val;
    }
    int mid = (cl + cr) / 2;
    return get(V[node].lef, cl, mid, tl, tr) + get(V[node].rig, mid + 1, cr, tl, tr);
}

int root[N];

void init(int _N, int A[], int B[]) {
    n = _N;
    for(int i = 0 ; i < n; i ++ ){
        segm.push_back(mp(A[i], B[i]));
        segt.push_back(mp(B[i], A[i]));
    }
    sort(segm.begin(), segm.end());
    sort(segt.begin(), segt.end());
    int iq = 0;
    root[0] = -1;
    int dash;
    for(int i = 1; i <= n; i ++ ){
        root[i] = root[i - 1];
        while(iq < segt.size() && segt[iq].fi <= i){
            dash = upd(root[i], 1, n, segt[iq].se, +1);
            root[i] = dash;
            iq ++ ;
        }
    }
}

const int C = 400;
ll dp[C];
ll low[C];

int compute(int lf, int rf){
    return get(root[rf], 1, n, lf, rf);
}

int can(int M, int K[]) {
    vector<int> lis;
    int m = M;
    for(int j = 0; j < m ; j ++ ){
        lis.push_back(K[j]);
    }
    sort(lis.begin(), lis.end());
    bool sol0 = true, sol1 = true;
    if(m >= C){
        ll cum = 0;
        for(auto x : lis) cum += x;
        if(cum > n) {
            sol0=false;
            return false;
        }
        priority_queue<int, vector<int>, greater<int>> cv;
        int iq = 0;
        for(auto x : lis){
            while(iq < segm.size() && segm[iq].fi <= x){
                cv.push(segm[iq].se);
                iq ++ ;
            }
            while(!cv.empty() && cv.top() < x)
                cv.pop();
            if(cv.size() < x){
                sol0=false;
                break;
            }
            for(int j = 0 ; j < x; j ++ ){
                cv.pop();
            }
        }
        return sol0;
    }
    else { // by hall
        ll comp;
        for(int j = 0 ; j < m ; j ++ ){
            dp[j] = n - lis[j] - compute(1, lis[j] - 1);
            for(int i = 0; i < j ; i ++ ){
                dp[j] = min(dp[j], dp[i] - lis[j] - compute(lis[i] + 1, lis[j] - 1));
            }
            comp = dp[j] - compute(lis[j] + 1, n);
            if(comp < 0){
                sol1=false;
                break;
            }
        }
        return sol1;
    }
	return sol0;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while(iq < segt.size() && segt[iq].fi <= i){
      |               ~~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:114:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             while(iq < segm.size() && segm[iq].fi <= x){
      |                   ~~~^~~~~~~~~~~~~
teams.cpp:120:26: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int, std::vector<int>, std::greater<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  120 |             if(cv.size() < x){
      |                ~~~~~~~~~~^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 3 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 368 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 380 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 2 ms 364 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 25180 KB Output is correct
2 Correct 76 ms 25176 KB Output is correct
3 Correct 74 ms 25176 KB Output is correct
4 Correct 79 ms 26584 KB Output is correct
5 Correct 51 ms 24920 KB Output is correct
6 Correct 55 ms 24804 KB Output is correct
7 Correct 51 ms 24792 KB Output is correct
8 Correct 49 ms 24792 KB Output is correct
9 Correct 44 ms 26200 KB Output is correct
10 Correct 44 ms 25816 KB Output is correct
11 Correct 43 ms 25688 KB Output is correct
12 Correct 42 ms 25076 KB Output is correct
13 Correct 55 ms 25176 KB Output is correct
14 Correct 54 ms 25304 KB Output is correct
15 Correct 70 ms 25176 KB Output is correct
16 Correct 70 ms 25176 KB Output is correct
17 Correct 49 ms 25432 KB Output is correct
18 Correct 52 ms 25432 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 25816 KB Output is correct
2 Correct 82 ms 25816 KB Output is correct
3 Correct 173 ms 29272 KB Output is correct
4 Correct 79 ms 26456 KB Output is correct
5 Correct 454 ms 25432 KB Output is correct
6 Correct 1014 ms 25432 KB Output is correct
7 Correct 56 ms 25432 KB Output is correct
8 Correct 734 ms 25432 KB Output is correct
9 Correct 44 ms 26328 KB Output is correct
10 Correct 64 ms 26288 KB Output is correct
11 Correct 236 ms 26352 KB Output is correct
12 Correct 885 ms 25944 KB Output is correct
13 Correct 280 ms 25968 KB Output is correct
14 Correct 193 ms 27608 KB Output is correct
15 Correct 176 ms 25944 KB Output is correct
16 Correct 171 ms 25816 KB Output is correct
17 Correct 312 ms 26092 KB Output is correct
18 Correct 280 ms 26072 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 504 ms 134724 KB Output is correct
2 Correct 506 ms 134596 KB Output is correct
3 Correct 806 ms 142940 KB Output is correct
4 Correct 504 ms 136388 KB Output is correct
5 Correct 2093 ms 134844 KB Output is correct
6 Correct 3507 ms 136832 KB Output is correct
7 Correct 279 ms 136644 KB Output is correct
8 Correct 2583 ms 137156 KB Output is correct
9 Correct 254 ms 141508 KB Output is correct
10 Correct 506 ms 139388 KB Output is correct
11 Correct 3030 ms 140268 KB Output is correct
12 Correct 2247 ms 136896 KB Output is correct
13 Correct 1093 ms 138564 KB Output is correct
14 Correct 815 ms 142916 KB Output is correct
15 Correct 707 ms 139460 KB Output is correct
16 Correct 688 ms 139844 KB Output is correct
17 Correct 921 ms 138948 KB Output is correct
18 Correct 839 ms 139144 KB Output is correct