oj.uz

Submission #424658

# Submission time Handle Problem Language Result Execution time Memory
424658 2021-06-12T08:51:58 Z 79brue Teams (IOI15_teams) C++14
100 / 100
 2732 ms 179224 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 58956 KB Output is correct
2 Correct 35 ms 58876 KB Output is correct
3 Correct 32 ms 58932 KB Output is correct
4 Correct 33 ms 59016 KB Output is correct
5 Correct 33 ms 58996 KB Output is correct
6 Correct 32 ms 59044 KB Output is correct
7 Correct 31 ms 59000 KB Output is correct
8 Correct 32 ms 58988 KB Output is correct
9 Correct 33 ms 58996 KB Output is correct
10 Correct 33 ms 58976 KB Output is correct
11 Correct 31 ms 58960 KB Output is correct
12 Correct 32 ms 59028 KB Output is correct
13 Correct 35 ms 58972 KB Output is correct
14 Correct 32 ms 59020 KB Output is correct
15 Correct 34 ms 58988 KB Output is correct
16 Correct 33 ms 58948 KB Output is correct
17 Correct 35 ms 58932 KB Output is correct
18 Correct 32 ms 58956 KB Output is correct
19 Correct 32 ms 58948 KB Output is correct
20 Correct 33 ms 58892 KB Output is correct
21 Correct 38 ms 58940 KB Output is correct
22 Correct 32 ms 58956 KB Output is correct
23 Correct 32 ms 58972 KB Output is correct
24 Correct 35 ms 58948 KB Output is correct
25 Correct 33 ms 59132 KB Output is correct
26 Correct 32 ms 58948 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 79480 KB Output is correct
2 Correct 127 ms 79832 KB Output is correct
3 Correct 132 ms 79704 KB Output is correct
4 Correct 134 ms 80480 KB Output is correct
5 Correct 61 ms 76720 KB Output is correct
6 Correct 56 ms 76784 KB Output is correct
7 Correct 58 ms 76684 KB Output is correct
8 Correct 57 ms 76784 KB Output is correct
9 Correct 64 ms 75736 KB Output is correct
10 Correct 69 ms 75704 KB Output is correct
11 Correct 66 ms 76652 KB Output is correct
12 Correct 70 ms 75796 KB Output is correct
13 Correct 76 ms 76700 KB Output is correct
14 Correct 89 ms 77436 KB Output is correct
15 Correct 120 ms 79172 KB Output is correct
16 Correct 119 ms 79356 KB Output is correct
17 Correct 75 ms 76752 KB Output is correct
18 Correct 67 ms 76736 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 79932 KB Output is correct
2 Correct 155 ms 79940 KB Output is correct
3 Correct 524 ms 83148 KB Output is correct
4 Correct 123 ms 80456 KB Output is correct
5 Correct 105 ms 77276 KB Output is correct
6 Correct 100 ms 77296 KB Output is correct
7 Correct 65 ms 77228 KB Output is correct
8 Correct 89 ms 77304 KB Output is correct
9 Correct 54 ms 75924 KB Output is correct
10 Correct 72 ms 76012 KB Output is correct
11 Correct 78 ms 76784 KB Output is correct
12 Correct 174 ms 76004 KB Output is correct
13 Correct 479 ms 78540 KB Output is correct
14 Correct 711 ms 82628 KB Output is correct
15 Correct 195 ms 81180 KB Output is correct
16 Correct 208 ms 81136 KB Output is correct
17 Correct 128 ms 78648 KB Output is correct
18 Correct 129 ms 78584 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 699 ms 171608 KB Output is correct
2 Correct 698 ms 171756 KB Output is correct
3 Correct 2027 ms 177672 KB Output is correct
4 Correct 685 ms 172604 KB Output is correct
5 Correct 276 ms 156740 KB Output is correct
6 Correct 268 ms 156612 KB Output is correct
7 Correct 182 ms 156612 KB Output is correct
8 Correct 262 ms 156720 KB Output is correct
9 Correct 152 ms 150504 KB Output is correct
10 Correct 252 ms 154132 KB Output is correct
11 Correct 314 ms 154004 KB Output is correct
12 Correct 789 ms 154140 KB Output is correct
13 Correct 1560 ms 162000 KB Output is correct
14 Correct 2732 ms 179224 KB Output is correct
15 Correct 782 ms 175300 KB Output is correct
16 Correct 757 ms 175240 KB Output is correct
17 Correct 411 ms 162560 KB Output is correct
18 Correct 405 ms 162568 KB Output is correct