Submission #530306

#	Time	Username	Problem	Language	Result	Execution time	Memory
530306		ajpiano	Teams (IOI15_teams)	C++17	0 / 100	1258 ms	97052 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

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

const int large = 5e5+5;


vector<pi> bit[large]; //r, val

void binit(){
    for(int i = 1; i < large; i++)
        bit[i].push_back({-large,0});
}

void add(int pos, int r){
    for(; pos < large; pos += pos&-pos)
        bit[pos].push_back({r,bit[pos].back().s+1});
}

int sum(int pos, int fr){
    int ans = 0;
    for(; pos > 0; pos -= pos&-pos){
        int l = 0, r = bit[pos].size();
        while(r-l > 1){
            int mid = (l+r)>>1;
            if(bit[pos][mid].f <= fr)
                l = mid;
            else r = mid;
        }
        ans += bit[pos][l].s;
    }
    return ans;
}

int sum(int l1, int l2, int r1, int r2){ //finds from (l1, l2], (r1, r2]
    return sum(l2,r2)-sum(l1,r2)-sum(l2,r1)+sum(l1, r1);
}

int n;
vector<int> a, b;

void init(int _n, int _a[], int _b[]){
    //input stuff
    n = _n; //a = _a; b = _b;
    for(int i = 0; i < n; i++){
        a.push_back(_a[i]);
        b.push_back(_b[i]);
    }
    //process information
    binit();
    vector<pi> ranges(n); //r,l
    for(int i = 0; i < n; i++){
        ranges[i] = {b[i],a[i]};
    }
    sort(ranges.begin(), ranges.end());
    for(auto &p: ranges){
        add(p.s,p.f);
    }
}

int can(int m, int k[]){
    //fix input
//    vector<int> k2 = k;
    vector<int> k2;
    for(int i = 0; i < m; i++) k2.push_back(k[i]);
    k2.push_back(0); k2.push_back(n+1);
    sort(k2.begin(), k2.end(), greater<int>());
    int carry = 0;
    bool good = 1;
    for(int i = 1; i <= m; i++){
        int nrem = k2[i];
        int sp = sum(k2[i+1], k2[i], k2[i]-1, k2[i-1]-1);
        nrem -= sp; nrem = max(nrem, 0);
        int tleft = sum(0, k2[i], k2[i]-1, n+1);
        carry += nrem;
        if(tleft < carry){
            good = 0; break;
        }
        carry -= sum(k2[i+1], k2[i], k2[i]-1, n+1);
        carry = max(0, carry);
    }
    if(!good) return 0;
    return 1;
}

//int main()
//{
//    ios_base::sync_with_stdio(0); cin.tie(0);
//    int _n; vector<int> _a,_b;
//    cin >> _n; _a.resize(_n); _b.resize(_n);
//    for(int i = 0; i < _n; i++) cin >> _a[i] >> _b[i];
//    init(_n,_a,_b);
//    int q; cin >> q;
//
//    for(int i = 0; i < q; i++){
//        int m; cin >> m;
//        vector<int> k(m);
//        for(int j = 0; j < m; j++) cin >> k[j];
//        cout << can(m,k) << "\n";
//    }
//    return 0;
//}

Compilation message (stderr)

teams.cpp: In function 'int sum(int, int)':
teams.cpp:30:37: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   30 |         int l = 0, r = bit[pos].size();
      |                        ~~~~~~~~~~~~~^~

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