oj.uz

Submission #241293

# Submission time Handle Problem Language Result Execution time Memory
241293 2020-06-23T17:47:10 Z Mercenary Jousting tournament (IOI12_tournament) C++14
100 / 100
 240 ms 12472 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 6 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 11 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 13 ms 896 KB Output is correct
5 Correct 12 ms 908 KB Output is correct
6 Correct 13 ms 896 KB Output is correct
7 Correct 11 ms 1024 KB Output is correct
8 Correct 11 ms 1024 KB Output is correct
9 Correct 9 ms 896 KB Output is correct
10 Correct 16 ms 896 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 6008 KB Output is correct
2 Correct 240 ms 12472 KB Output is correct
3 Correct 106 ms 9592 KB Output is correct
4 Correct 180 ms 12408 KB Output is correct
5 Correct 184 ms 12148 KB Output is correct
6 Correct 203 ms 11384 KB Output is correct
7 Correct 188 ms 12408 KB Output is correct
8 Correct 196 ms 12464 KB Output is correct
9 Correct 87 ms 9852 KB Output is correct
10 Correct 111 ms 10616 KB Output is correct