oj.uz

Submission #543401

# Submission time Handle Problem Language Result Execution time Memory
543401 2022-03-30T13:22:38 Z Lobo Jousting tournament (IOI12_tournament) C++17
100 / 100
 167 ms 14656 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 1e5+10;

int n, lz[4*maxn], trlz[4*maxn], L[maxn], R1[maxn], ps[maxn], last[maxn], nx[maxn];
pair<int,int> tr[4*maxn];

void flush(int no, int l, int r) {
    if(lz[no] == 0) return;
    trlz[no]+= lz[no];

    if(l != r) {
        int f1 = 2*no;
        int f2 = 2*no+1;
        lz[f1]+= lz[no];
        lz[f2]+= lz[no];
    }
    lz[no] = 0;
}

void attlz(int no, int l, int r, int L, int R, int val) {
    flush(no,l,r);
    if(l > R || r < L) return;
    else if(l >= L && r <= R) {
        lz[no] = val;
        flush(no,l,r);
        return;
    }

    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;

    attlz(f1,l,mid,L,R,val);
    attlz(f2,mid+1,r,L,R,val);
    trlz[no] = max(trlz[f1],trlz[f2]);
}

int findseg(int no, int l, int r, int val) {
    if(l == r) {
        return l;
    }

    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;
    flush(no,l,r);
    flush(f1,l,mid);
    flush(f2,mid+1,r);

    if(trlz[f1] < val) {
        return findseg(f2,mid+1,r,val);
    }
    else {
        return findseg(f1,l,mid,val);
    }
}

void attmx(int no, int l, int r, int pos, int val, int id) {
    if(l > pos || r < pos) return;
    else if(l == r) {
        tr[no] = max(tr[no],mp(val,id));
        return;
    }

    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;
    attmx(f1,l,mid,pos,val,id);
    attmx(f2,mid+1,r,pos,val,id);
    tr[no] = max(tr[f1],tr[f2]);
}

pair<int,int> qrrmx(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return mp(0,0);
    else if(l >= L && r <= R) {
        return tr[no];
    }
    int f1 = 2*no;
    int f2 = 2*no+1;
    int mid = (l+r)/2;
    return max(qrrmx(f1,l,mid,L,R),qrrmx(f2,mid+1,r,L,R));
}

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

    n = N;
    for(int i = 0; i < N-1; i++) {
        if(K[i] > R) {
            ps[i] = 1;
        }
        if(i != 0) ps[i]+= ps[i-1];
    }

    for(int i = 0; i < n; i++) {
        attlz(1,0,N-1,i,i,i);
        last[i] = i;
    }


    for(int i = 0; i < C; i++) {
        //encontra o proximo do cara
        L[i] = findseg(1,0,n-1,S[i]);
        R1[i] = last[findseg(1,0,n-1,E[i])];
        // cout << E[i] << " " << findseg(1,0,n-1,E[i]) << endl;

        if(L[i] != R1[i]) attlz(1,0,n-1,L[i]+1,R1[i],-n);
        if(R1[i] != n-1) attlz(1,0,n-1,R1[i]+1,n-1,-(E[i]-S[i]));

        last[L[i]] = R1[i];

        // cout << i << " " << S[i] << "," << E[i] << " " << L[i] << "," << R1[i] << endl;
    }


    vector<pair<int,int>> v;
    for(int i = 0; i < C; i++) {
        v.pb(mp(R1[i]-L[i],i));
    }

    sort(all(v));
    for(int i = 0; i < C; i++) {
        int id = v[i].sc;
        nx[id] = L[id];
        if(ps[R1[id]-1] - (L[id] == 0 ? 0 : ps[L[id]-1]) > 0) continue;

        auto qr = qrrmx(1,0,n,L[id],R1[id]);
        nx[id] = -qr.sc;
        if(qr.fr == 0) nx[id] = L[id];
        attmx(1,0,n-1,L[id],qr.fr+1,-nx[id]);
    }

    auto qr = qrrmx(1,0,n-1,0,n-1);
    if(qr.fr == 0) {
        return 0;
    }
    int32_t ans = -qr.sc;
    return ans;

}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
//     // freopen("out.out", "w", stdout);

//     int32_t N, C, R; cin >> N >> C >> R;
//     int32_t *K, *S, *E;
//     K = (int32_t*) malloc((N-1) * sizeof(int32_t));
//     S = (int32_t*) malloc(C * sizeof(int32_t));
//     E = (int32_t*) malloc(C * sizeof(int32_t));

//     for(int i = 0; i < N-1; i++) {
//         cin >> K[i];
//     }
//     for(int i = 0; i < C; i++) {
//         cin >> S[i] >> E[i];
//     }
//     cout << GetBestPosition(N,C,R,K,S,E) << endl;
// }

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 308 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 7 ms 1108 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 7 ms 1220 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 6 ms 1152 KB Output is correct
7 Correct 7 ms 1212 KB Output is correct
8 Correct 7 ms 1284 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 7 ms 1348 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 7004 KB Output is correct
2 Correct 158 ms 13220 KB Output is correct
3 Correct 47 ms 7476 KB Output is correct
4 Correct 167 ms 13684 KB Output is correct
5 Correct 158 ms 13328 KB Output is correct
6 Correct 138 ms 14656 KB Output is correct
7 Correct 160 ms 13704 KB Output is correct
8 Correct 155 ms 13360 KB Output is correct
9 Correct 32 ms 6468 KB Output is correct
10 Correct 41 ms 8760 KB Output is correct