Submission #384117

#	Time	Username	Problem	Language	Result	Execution time	Memory
384117		doowey	Teams (IOI15_teams)	C++14	100 / 100	3507 ms	142940 KiB

teams

#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 (stderr)

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 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23