Submission #530594

#	Time	Username	Problem	Language	Result	Execution time	Memory
530594		ajpiano	Teams (IOI15_teams)	C++17	100 / 100	1905 ms	115312 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 = 0; 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 valfnd(int node, int r1, int r2){
    int x = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r2+1,-1)))->s;
    int y = prev(lower_bound(bit[node].begin(), bit[node].end(),make_pair(r1+1, -1)))->s;
    return x-y;
}

int binsearch(int l2, int r1, int r2, int val){
    int x = valfnd(l2,r1,r2);
    if(x < val) return binsearch(l2-(l2&-l2), r1,r2,val-x);
    int dif = l2&-l2;
    for(dif >>= 1; dif > 0; dif >>= 1){
        x -= valfnd(l2-dif, r1, r2);
        if(x < val){
            val -= x; return binsearch(l2-dif, r1, r2, val);
        }
    }
    return l2;
}

int n;

void init(int _n, int _a[], int _b[]){
    //input stuff
    n = _n; //a = _a; b = _b;
    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()); //increasing r order
    for(auto &p: ranges){
        add(p.s,p.f);
    }
}

int can(int m, int k[]){
    //fix input
    vector<int> k2;
    vector<pair<pi, int>> hchange = {{{0,n+1},0}}; //{x,y}, add at place
    for(int i = 0; i < m; i++) k2.push_back(k[i]);
    sort(k2.begin(), k2.end(), greater<int>());
    for(int i = 0; i < m; i++){
        int rem = k2[i];
        int rp = k2[i];
        while(rem > 0 && !hchange.empty()){
            //remove if protected region is no longer valid
            if(hchange.back().f.f > k2[i]){
                hchange.pop_back(); continue;
            }
            //find value of current protected region
            int ctop = hchange.back().f.s-1, cleft = hchange.back().f.f, cadd = hchange.back().s;
            int x = sum(cleft-1, rp, k2[i]-1, ctop)+cadd;

            //Move on if current region has too little
            if(rem > x){
                rem -= x; rp = cleft-1;
                hchange.pop_back(); continue;
            }
            //Current region has just enough
            int boval = sum(cleft, rp, k2[i]-1, ctop);
            if(rem > boval){
                hchange.pop_back();
                hchange.push_back({{cleft, k2[i]}, x-rem});
                rem = 0; continue;
            }
            //binary search to find position
            int l = binsearch(rp, k2[i]-1, ctop, rem);
            x = sum(l-1, rp, k2[i]-1, ctop);
            hchange.push_back({{l,k2[i]}, x-rem});
            rem = 0;
            continue;
        }
        if(rem > 0) return 0;
    }
    return 1;
}

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