oj.uz

Submission #17150

# Submission time Handle Problem Language Result Execution time Memory
17150 2015-11-07T07:05:14 Z murat Jousting tournament (IOI12_tournament) C++
100 / 100
 539 ms 136824 KB 
#include<bits/stdc++.h>

using namespace std;

#define dbgs(x) cerr << (#x) << " --> " << (x) << ' '
#define dbg(x) cerr << (#x) << " --> " << (x) << endl

#define foreach(i,x) for(type(x)i=x.begin();i!=x.end();i++)
#define FOR(ii,aa,bb) for(int ii=aa;ii<=bb;ii++)
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)

#define type(x) __typeof(x.begin())

#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)

#define pb push_back
#define mp make_pair

#define nd second
#define st first

#define endl '\n'

typedef pair < int ,int > pii;

typedef long long ll;

const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 1e6 + 5;

int L[N], ST[N << 2], val[N], R, mx[N << 2], a[N], n, m, x, y, z, t, cc, ans, l[N], r[N];
vector< pii > s[N], f[N];
pii ST3[N << 2];

int init(int k, int bas, int son) {
    if(bas == son) return ST[k] = 1;
    return ST[k] = init(sol, bas, orta) + init(sag, orta+1, son);
}

void push(int k) {
    if(!L[k]) return ;
    ST[sol] = ST[sag] = 0;
    L[sol] = L[sag] = 1;
    L[k] = 0;
}

int query(int k, int bas, int son, int x) {
    if(bas > x) return 0;
    if(son <= x) return ST[k];
    push(k);
    return query(sag, orta+1, son, x) + query(sol, bas, orta, x);
}

int update(int k, int bas, int son, int x) {
    if(bas > x || son < x) return ST[k];
    if(bas == son) return ST[k] = 1;
    push(k);
    return ST[k] = update(sol, bas, orta, x) + update(sag, orta+1, son, x);
}

int update(int k, int bas, int son, int x, int y) {
    if(bas > y || son < x) return ST[k];
    if(x <= bas && son <= y) {
        L[k] = 1;
        return ST[k] = 0;
    }
    push(k);
    return ST[k] = update(sol, bas, orta, x, y) + update(sag, orta+1, son, x, y);
}

int init2(int k, int bas, int son) {
    if(bas == son) return mx[k] = a[bas];
    return mx[k] = max(init2(sag, orta+1, son), init2(sol, bas, orta));
}

int query2(int k, int bas, int son, int x, int y) {
    if(bas > y || son < x) return 0;
    if(x <= bas && son <= y) return mx[k];
    return max(query2(sol, bas, orta, x, y), query2(sag, orta+1, son, x, y));
}

pii update3(int k, int bas, int son, int x, int t) {
    if(bas > x || son < x) return ST3[k];
    if(bas == son) return ST3[k] = mp(t, t != 0);
    update3(sol, bas, orta, x, t);
    update3(sag, orta + 1, son, x, t);
    return ST3[k] = mp(max(ST3[sol].st, ST3[sag].st), ST3[sol].nd + ST3[sag].nd);
}

int take3(int k, int bas, int son) {
    if(bas == son) return ST3[k].nd && ST3[k].st <= R;
    if(ST3[sol].st <= R) return take3(sag, orta+1, son) + ST3[sol].nd;
    return take3(sol, bas, orta);
}

int take(int x) {
    int bas = 1, son = n;
    if(!x) return 0;
    while(bas < son) {
        int ort = bas + son >> 1;
        if(bas == orta) ort++;
        if(query(1, 1, n, ort) <= x) bas = ort;
        else son = ort - 1;
    }
    return bas;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

    n = N;

    for(int i = 1; i < n; i++) {
        val[i] = 1;
        a[i] = ++K[i-1];
    } ++R; val[n] = 1;

    ::R = R;

    init(1, 1, n);
    init2(1, 1, n);

    vector< pair< pii , int > > vv;

    for(int i = 1; i <= C; i++) {
        int x = S[i-1] + 1,
            y = E[i-1] + 1;
        int xx = take(x-1) + 1;
        int yy = take(y);
        int tt = 0;
        update(1, 1, n, xx, yy);
        update(1, 1, n, xx);
        int mx = query2(1, 1, n, xx, yy-1);
        vv.pb(mp(mp(xx, yy-1), mx));
        s[xx].pb(mp(i, mx));
        f[yy-1].pb(mp(i, mx));
    }

    int ans = 0, aaa = 0;

    for(int i = 1; i <= n; i++) {
        foreach(it, s[i]) {
            update3(1, 1, C, it->st, it->nd);
        }
        int cc = take3(1, 1, C);
        if(cc > ans) { ans = cc; aaa = i - 1; }
        foreach(it, f[i]) {
            update3(1, 1, C, it->st, 0);
        }
    }

    return aaa;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 130632 KB Output is correct
2 Correct 8 ms 130632 KB Output is correct
3 Correct 18 ms 130632 KB Output is correct
4 Correct 15 ms 130632 KB Output is correct
5 Correct 11 ms 130632 KB Output is correct
6 Correct 11 ms 130632 KB Output is correct
7 Correct 15 ms 130632 KB Output is correct
8 Correct 11 ms 130632 KB Output is correct
9 Correct 17 ms 130632 KB Output is correct
10 Correct 17 ms 130632 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 130632 KB Output is correct
2 Correct 31 ms 130984 KB Output is correct
3 Correct 22 ms 130632 KB Output is correct
4 Correct 26 ms 130984 KB Output is correct
5 Correct 23 ms 130980 KB Output is correct
6 Correct 15 ms 130768 KB Output is correct
7 Correct 21 ms 130984 KB Output is correct
8 Correct 34 ms 130984 KB Output is correct
9 Correct 15 ms 130632 KB Output is correct
10 Correct 25 ms 131000 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 132780 KB Output is correct
2 Correct 539 ms 136824 KB Output is correct
3 Correct 57 ms 131432 KB Output is correct
4 Correct 517 ms 136824 KB Output is correct
5 Correct 529 ms 136652 KB Output is correct
6 Correct 401 ms 134920 KB Output is correct
7 Correct 514 ms 136820 KB Output is correct
8 Correct 532 ms 136820 KB Output is correct
9 Correct 26 ms 131024 KB Output is correct
10 Correct 77 ms 131452 KB Output is correct