oj.uz

Submission #31104

# Submission time Handle Problem Language Result Execution time Memory
31104 2017-08-10T01:36:54 Z h0ngjun7 Jousting tournament (IOI12_tournament) C++14
0 / 100
 49 ms 6324 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5928 KB Output is correct
2 Incorrect 0 ms 5928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 5928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 6324 KB Output isn't correct
2 Halted 0 ms 0 KB -