Submission #31104

#	Time	Username	Problem	Language	Result	Execution time	Memory
31104		h0ngjun7	Jousting tournament (IOI12_tournament)	C++14	0 / 100	49 ms	6324 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
struct data{
    int x, y;
}q[100100];
int a[100100], N, C, R, tree[300100], ans[100100], tree1[300100];
 
void update(int n, int s, int e, int si, int ei, int v){
    if(s > ei || e < si) return;
    if(s >= si && e <= ei) {
        tree[n] = v; return;
    }
    int lch = 2*n, rch = lch + 1, m = (s+e)>>1;
    update(lch, s, m, si, ei, v);
    update(rch, m+1, e, si, ei, v);
    tree[n] = max(tree[lch], tree[rch]);
}
 
int query(int n, int s, int e, int si, int ei){
    if(s > ei || e < si) return -1;
    if(s >= si && e <= ei) return tree[n];
    int lch = 2*n, rch = lch + 1, m = (s+e)>>1;
    return max(query(lch, s, m, si, ei), query(rch, m+1, e, si, ei));
}
 
void update1(int n, int s, int e, int si, int ei, int v){
    if(s > ei || e < si) return;
    if(s >= si && e <= ei){
        tree1[n] += v; return;
    }
    int lch = 2*n, rch = lch + 1, m = (s+e)>>1;
    update1(lch, s, m, si, ei, v);
    update1(rch, m+1, e, si, ei, v);
}
 
int query1(int n, int s, int e, int si, int ei){
    if(s > ei || e < si) return 0;
    if(s >= si && e <= ei) return tree1[n];
    int lch = 2*n, rch = lch + 1, m = (s+e)>>1;
    return tree1[n] + query1(lch, s, m, si, ei) + query1(rch, m+1, e, si, ei);
}
int GetBestPosition(int _N, int _C, int _R, int *K, int *S, int *E) {
    int i, ret = 0;
    N = _N; C = _C; R = _R;
    for(i=0; i<N; i++) a[i+1] = K[i], update(1, 1, N, i+1, i+1, a[i+1]);
    q[0].x = S[0]+1; q[0].y = E[0]+1;
    update1(1, 1, N, S[0]+1, N+1, q[0].y - q[0].x);
    for(i=1; i<C; i++){
        q[i].x = S[i]+1; q[i].y = E[i]+1;
        q[i].x += query1(1, 1, N, q[i].x-1, q[i].x-1);
        q[i].y += query1(1, 1, N, q[i].y, q[i].y);
        update1(1, 1, N, S[i]+1, N+1, E[i] - S[i]);
    }
    for(i=0; i<C; i++){
        if(query(1, 1, N, q[i].x, q[i].y-1) < R){
            ans[q[i].x]++; ans[q[i].y+1]--;
        }
    }
    for(i=1; i<=N+1; i++){
        ans[i] += ans[i-1];
        if(ans[ret] < ans[i]) ret = i;
    }
    return ret-1;
}

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