Submission #384086

#	Time	Username	Problem	Language	Result	Execution time	Memory
384086		doowey	Teams (IOI15_teams)	C++14	34 / 100	4064 ms	138560 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] = V[node];
    V[cid].val += vv;
    cur ++ ;
    if(cl == cr) return cid;
    int mid = (cl + cr) / 2;
    if(id <= mid){
        int go = V[node].lef;
        V[node].lef = upd(go, cl, mid, id, vv);
    }
    else{
        int go = V[node].rig;
        V[node].rig = upd(go, mid + 1, cr, id, vv);
    }
    return cid;
}

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

const int C = 1;

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;

    }
	return 0;
}

Compilation message (stderr)

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

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