Submission #241293

#	Time	Username	Problem	Language	Result	Execution time	Memory
241293		Mercenary	Jousting tournament (IOI12_tournament)	C++14	100 / 100	240 ms	12472 KiB

tournament

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define taskname "A"
#define pb	push_back
#define mp 	make_pair


typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int maxn = 1e5 + 5;
ii s[maxn * 4];
int lz[maxn * 4];
void build(int x , int l , int r){
    s[x] = mp(0 , -l);
    if(l == r)return;
    int mid = l + r >> 1;
    build(x * 2 , l , mid);
    build(x * 2 + 1 , mid + 1 , r);
}
void push(int x , bool key){
    if(lz[x] == -1)s[x].first = -1e9;
    else s[x].first += lz[x];
    if(key){
        if(lz[x] == -1)lz[x * 2] = lz[x * 2 + 1] = -1;
        else lz[x * 2] += lz[x] , lz[x * 2 + 1] += lz[x];
    }
    lz[x] = 0;
}
void update(int x , int l , int r , int L , int R , int val){
    push(x , l != r);
    if(l > R || L > r)return;
    if(L <= l && r <= R){
        if(val == -1)lz[x] = -1;
        else lz[x] += val;
        push(x , l != r);
        return;
    }
    int mid = l + r >> 1;
    update(x * 2 , l , mid , L , R , val);
    update(x * 2 + 1 , mid + 1 , r , L , R , val);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
}
int GetBestPosition(int n , int q , int cur , int* a , int* L , int* R) {
    build(1 , 0 , n - 1);
    ordered_set s;
    vector<ii> range(n);
    vector<int> sum(n , 0);
    for(int i = 0 ; i < n ; ++i){
        range[i] = mp(i,i);
        s.insert(i);
    }
    vector<int> pos;
    for(int i = 0 ; i < n - 1 ; ++i){
        if(a[i] > cur)pos.pb(i);
    }
    pos.pb(n);
    ii best = mp(0 , 0);
    for(int i = 0 ; i < q ; ++i){
        int len = R[i] - L[i];
        int tmp = 0;
        while(len--){
            auto now = *s.find_by_order(L[i] + 1);
            tmp = max(tmp , range[now].second);
            s.erase(now);
        }
        auto now = *s.find_by_order(L[i]);
        range[now].second = tmp;
        auto [l , r] = range[now];
        tmp = *lower_bound(pos.begin(),pos.end(),l);
        if(tmp < r){
            update(1 , 0 , n , l , r , -1);
        }else update(1 , 0 , n - 1,  l , r , 1);
        best = max(best,::s[1]);
    }
    return -best.second;
}

#ifdef LOCAL

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define inbuf_len 1 << 16
#define outbuf_len 1 << 16

int main() {
    freopen("A.INP","r",stdin);
  int tmp;
  /* Set input and output buffering */
  int N, C, R;
  int *K, *S, *E;
  tmp = scanf("%d %d %d", &N, &C, &R);
  assert(tmp == 3);
  K = (int*) malloc((N-1) * sizeof(int));
  S = (int*) malloc(C * sizeof(int));
  E = (int*) malloc(C * sizeof(int));
  int i;
  for (i = 0; i < N-1; i++) {
    tmp = scanf("%d", &K[i]);
    assert(tmp == 1);
  }
  for (i = 0; i < C; i++) {
    tmp = scanf("%d %d", &S[i], &E[i]);
    assert(tmp == 2);
  }

  printf("%d\n", GetBestPosition(N, C, R, K, S, E));

  return 0;

}
#endif // LOCAL

Compilation message (stderr)

tournament.cpp: In function 'void build(int, int, int)':
tournament.cpp:22:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
tournament.cpp: In function 'void update(int, int, int, int, int, int)':
tournament.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:74:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
         auto [l , r] = range[now];
              ^

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51