Submission #119077

#	Time	Username	Problem	Language	Result	Execution time	Memory
119077		oolimry	Teams (IOI15_teams)	C++14	13 / 100	4130 ms	382048 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int n;
ii arr[1000005];
multiset<ii> tree[1000005];

ii query(int i){
    ii mv = ii(102345678,0);
    i += n;
    while(i > 0){
        if(!tree[i].empty()){
            ii x = *tree[i].begin();
            mv = min(x,mv);
        }
        i >>= 1;
    }
    return mv;
}

ii add(int l, int r, ii x){
    for(l += n, r += n;l < r;l >>= 1, r >>= 1){
        if(l&1){
            tree[l].insert(x);
            l++;
        }
        if(r&1){
            r--;
            tree[r].insert(x);
        }
    }
}
ii era(int l, int r, ii x){
    for(l += n, r += n;l < r;l >>= 1, r >>= 1){
        if(l&1){
            tree[l].erase(tree[l].find(x));
            l++;
        }
        if(r&1){
            r--;
            tree[r].erase(tree[r].find(x));
        }
    }
}
void init(int N, int A[], int B[]) {
    n = N;
    for(int i = 0;i < n;i++){
        arr[i] = {B[i],A[i]};
    }
    sort(arr,arr+n);
    for(int i = 0;i < n;i++){
        int r = arr[i].first;
        int l = arr[i].second;
        add(l,r+1,{r,l});
    }
}

int can(int M, int K[]) {
    int m = M;
    int s = 0;
    for(int i = 0;i < m;i++) s += K[i];
    if(s > n) return 0;

    int tasks[s];
    int cnt = 0;
    for(int i = 0;i < m;i++){
        for(int j = 0;j < K[i];j++){
            tasks[cnt] = K[i];
            cnt++;
        }
    }
    sort(tasks,tasks+s);
    vector<ii> removed;
    for(int i = 0;i < s;i++){
        int x = tasks[i];
        ii u = query(x);
        //cout << u.first << " " << u.second << "\n";
        if(u.first == 102345678){
            return 0;
        }
        int l = u.second;
        int r = u.first;
        era(l,r+1,ii(r,l));
        removed.push_back(ii(r,l));
    }

    for(int i = 0;i < removed.size();i++){
        int r = removed[i].first;
        int l = removed[i].second;
        add(l,r+1,{r,l});
    }
	return 1;
}

Compilation message (stderr)

teams.cpp: In function 'ii add(int, int, ii)':
teams.cpp:33:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
teams.cpp: In function 'ii era(int, int, ii)':
teams.cpp:45:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i < removed.size();i++){
                   ~~^~~~~~~~~~~~~~~~

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