Submission #384089

#	Time	Username	Problem	Language	Result	Execution time	Memory
384089		doowey	Teams (IOI15_teams)	C++14	0 / 100	2067 ms	137044 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;

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]));
    }
    sort(segm.begin(), segm.end());
    int iq = 0;
    root[0] = -1;
    int dash;
    for(int i = 1; i <= n; i ++ ){
        root[i] = root[i - 1];
        while(iq < segm.size() && segm[iq].fi <= i){
            dash = upd(root[i], 1, n, segm[iq].se, +1);
            root[i] = dash;
            iq ++ ;
        }
    }
}

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

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());
    if(m >= C){
        ll cum = 0;
        for(auto x : lis) cum += x;
        if(cum > n) return 0;
        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) return false;
            for(int j = 0 ; j < x; j ++ ){
                cv.pop();
            }
        }
        return true;
    }
    else{ // by hall
        ll self;
        for(int j = 0 ; j < m ; j ++ ){
            self = get(root[lis[j]], 1, n, lis[j], n);
            dp[j] = self - K[j];
            if(dp[j] < 0) return 0;
            for(int i = 0 ; i < j ; i ++ ){
                dp[j] = min(dp[j], dp[i] + self - K[j] - get(root[lis[i]], 1, n, lis[j], n));
            }
            if(dp[j] < 0) return 0;
        }
        return 1;
    }
	return 0;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:77: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]
   77 |         while(iq < segm.size() && segm[iq].fi <= i){
      |               ~~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:103: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]
  103 |             while(iq < segm.size() && segm[iq].fi <= x){
      |                   ~~~^~~~~~~~~~~~~
teams.cpp:109: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]
  109 |             if(cv.size() < x) return false;
      |                ~~~~~~~~~~^~~

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