Submission #424658

#	Time	Username	Problem	Language	Result	Execution time	Memory
424658		79brue	Teams (IOI15_teams)	C++14	100 / 100	2732 ms	179224 KiB

teams

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

using namespace std;

typedef long long ll;
const ll D = 1000000000;

struct segTree{
    vector<ll> tree[2000002];

    void init(int i, int l, int r){
        if(l==r){
            sort(tree[i].begin(), tree[i].end());
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i].resize((int)tree[i*2].size() + (int)tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    void addPoint(int i, int l, int r, int x, ll y){
        if(l==r){
            tree[i].push_back(y);
            return;
        }
        int m = (l+r)>>1;
        if(x <= m) addPoint(i*2, l, m, x, y);
        else addPoint(i*2+1, m+1, r, x, y);
    }

    int query(int i, int l, int r, int s, int e, ll vl, ll vr){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e){
            return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
        }
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e, vl, vr) + query(i*2+1, m+1, r, s, e, vl, vr);
    }

    pair<int, int> findLim(int i, int l, int r, int x, ll s, ll e, int &lim){
        if(l==r){
            int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
            if(tret <= lim){
                lim -= tret;
                return make_pair(-1, -1);
            }
            return make_pair(l-1, lim);
        }
        int m = (l+r)>>1;
        if(x>m) return findLim(i*2+1, m+1, r, x, s, e, lim);

        if(x <= l){
            int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
            if(tret <= lim){
                lim -= tret;
                return make_pair(-1, -1);
            }
        }

        auto tmp = findLim(i*2, l, m, x, s, e, lim);
        if(tmp.first >= 0) return tmp;
        return findLim(i*2+1, m+1, r, x, s, e, lim);
    }
} tree;
vector<ll> occ[500002];

int n;
pair<ll, int> p[500002];

void init(int N, int A[], int B[]){
    n = N;
    for(int i=0; i<n; i++){
        p[i] = make_pair(D*A[i] + i, B[i]);
        occ[p[i].second].push_back(p[i].first);
        tree.addPoint(1, 1, n, p[i].second, p[i].first);
    }
    tree.init(1, 1, n);

    for(int i=1; i<=n; i++) sort(occ[i].begin(), occ[i].end());
}

int k;
int arr[200002];
stack<pair<ll, int> > stk;

int can(int M, int K[]){
    k = M;
    for(int i=1; i<=k; i++) arr[i] = K[i-1];
    sort(arr+1, arr+k+1);

    while(!stk.empty()) stk.pop();
    stk.push(make_pair(0, n));

    for(int i=1; i<=k; i++){
        int x = arr[i], lim = arr[i];
        while(i<k && arr[i] == arr[i+1]){
            i++;
            x += arr[i];
            if(x>n) return false;
        }

        while(!stk.empty() && stk.top().second < arr[i]) stk.pop();

        while(!stk.empty()){
            pair<ll, int> tmp = stk.top();
            int ret = tree.query(1, 1, n, lim, tmp.second, tmp.first+1, D*arr[i]+(D-1));
            if(ret > x) break;
            stk.pop();
            x -= ret;
            lim = tmp.second+1;
        }

        if(stk.empty()){
            if(x) return false;
            stk.push(make_pair(D*arr[i]+(D-1), n));
            continue;
        }

        pair<ll, int> p = stk.top();
        pair<int, int> tmp = tree.findLim(1, 1, n, lim, p.first+1, D*arr[i]+(D-1), x);
        int bx = tmp.first;

        if(x){
            auto it = lower_bound(occ[bx+1].begin(), occ[bx+1].end(), p.first+1) + (x-1);
            if(stk.top().second == bx+1) stk.pop();
            stk.push(make_pair(*it, bx+1));
        }
        if(stk.top().second == bx) stk.pop();
        stk.push(make_pair(D*arr[i]+(D-1), bx));
    }

    return true;
}

Compilation message (stderr)

teams.cpp: In member function 'int segTree::query(int, int, int, int, int, ll, ll)':
teams.cpp:37:68: warning: conversion from '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   37 |             return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In member function 'std::pair<int, int> segTree::findLim(int, int, int, int, ll, ll, int&)':
teams.cpp:45:71: warning: conversion from '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   45 |             int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:56:71: warning: conversion from '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   56 |             int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
      |                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:122:23: warning: declaration of 'p' shadows a global declaration [-Wshadow]
  122 |         pair<ll, int> p = stk.top();
      |                       ^
teams.cpp:71:15: note: shadowed declaration is here
   71 | pair<ll, int> p[500002];
      |               ^

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