oj.uz

답안 #768860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
768860 2023-06-28T19:31:24 Z keta_tsimakuridze 마상시합 토너먼트 (IOI12_tournament) C++14
0 / 100
 91 ms 6776 KB 
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
int lz[4 * N], t[4 * N], fw[N];
void upd(int u, int id, int l, int r) {
    if(l > id || r < id) return;
    if(l == r) {
        t[u] ^= 1;
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, id, l, mid); upd(2 * u + 1, id, mid + 1, r);
    t[u] = t[2 * u] + t[2 * u + 1];
}
int get(int u, int l, int r, int id) {
    if(l == r) return l;
    int mid = (l + r) / 2;
    if(t[2 * u] >= id) return get(2 * u, l, mid, id);
    return get(2 * u + 1, mid + 1, r, id - t[2 * u]);
}
void upd(int id, int v) {
    ++id;
    for(id; id <= n; id += id & (-id)) fw[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += fw[id];
    return ans;
}
int GetBestPosition(int nn, int C, int R, int *K, int *ST, int *E) {
    set<int> s, S, bad;
    n = nn;
    for(int i = 0; i < n; i++) s.insert(i), S.insert(i), upd(1, i, 0, n - 1);
    for(int i = 0; i < n - 1; i++) {
        if(K[i] > R) bad.insert(i);
    }
    bad.insert(n + 1); s.insert(n + 1); S.insert(n + 1);
    int ans = 0;
    for(int i = 0; i < C; i++) {
        ST[i] = (ST[i] == 0 ? 0 : get(1, 0, n - 1, ST[i]) + 1); E[i] = get(1, 0, n - 1, E[i] + 1);;
        while(*s.upper_bound(ST[i] - 1) <= E[i]) {
            int x = *s.upper_bound(ST[i] - 1);
            s.erase(x);
            upd(1, x, 0, n - 1);
        }
        upd(1, E[i], 0, n - 1); s.insert(E[i]);

        if(*bad.upper_bound(ST[i] - 1) >= E[i]) upd(ST[i], 1), upd(E[i] + 1, -1);
        else {
            while(*S.upper_bound(ST[i] - 1) <= E[i]) {
                ans = max(ans, get(*S.upper_bound(ST[i] - 1)));
                S.erase(*S.upper_bound(ST[i] - 1));
            }
        }
    }
    while(S.size()) ans = max(ans, get(*S.begin())), S.erase(*S.begin());
    return ans;
}

Compilation message

tournament.cpp: In function 'void upd(int, int)':
tournament.cpp:24:9: warning: statement has no effect [-Wunused-value]
   24 |     for(id; id <= n; id += id & (-id)) fw[id] += v;
      |         ^~
tournament.cpp: In function 'int get(int)':
tournament.cpp:28:9: warning: statement has no effect [-Wunused-value]
   28 |     for(id; id >= 1; id -= id & (-id)) ans += fw[id];
      |         ^~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 91 ms 6776 KB Output isn't correct
2 Halted 0 ms 0 KB -