Submission #1111750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111750		PagodePaiva	Jousting tournament (IOI12_tournament)	C++17	17 / 100	586 ms	1616 KiB

tournament

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 5010;

struct Segtremax{
    pair <int, int> tree[4*MAXN]; int lazy[4*MAXN];
    pair <int, int> join(pair <int, int> a, pair <int, int> b){
        if(a.first < b.first) return b;
        return a;
    }
    void unlazy(int node, int l, int r){
        if(lazy[node] == -1) return;
        tree[node].first = lazy[node];
        if(l != r){
            lazy[2*node] = max(lazy[2*node], lazy[node]);
            lazy[2*node+1] = max(lazy[2*node+1], lazy[node]);
        }
        lazy[node] = -1;
    }
    void build(int node, int l, int r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = {0, l};
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1,mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(int node, int l, int r, int tl, int tr, int val){
        if(l > r) return;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    pair <int, int> query(int node, int l, int r, int tl, int tr){
        if(l > r) return {-1, 0};
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return {-1, 0};
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} seg;

struct Segtresum{
    int tree[4*MAXN], lazy[4*MAXN];
    int join(int a, int b){
        return a+b;
    }
    void unlazy(int node, int l, int r){
        if(lazy[node] == -1) return;
        tree[node] = (r-l+1)*lazy[node];
        if(l != r){
            lazy[2*node] = lazy[node];
            lazy[2*node+1] = lazy[node];
        }
        lazy[node] = -1;
    }
    void build(int node, int l, int r){
        lazy[node] = -1;
        if(l == r){
            tree[node] = 1;
            return;
        }
        int mid = (l+r)/2;
        build(2*node, l, mid);
        build(2*node+1,mid+1, r);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    void update(int node, int l, int r, int tl, int tr, int val){
        if(l > r) return;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return;
        if(l <= tl and tr <= r){
            lazy[node] = val;
            unlazy(node, tl, tr);
            return;
        }
        int mid = (tl+tr)/2;
        update(2*node, l, r, tl, mid, val);
        update(2*node+1, l, r, mid+1, tr, val);
        tree[node] = join(tree[2*node], tree[2*node+1]);
        return;
    }
    int query(int node, int l, int r, int tl, int tr){
        if(l > r) return 0;
        unlazy(node, tl, tr);
        if(l > tr or tl > r) return 0;
        if(l <= tl and tr <= r) return tree[node];
        int mid = (tl+tr)/2;
        return join(query(2*node, l,r,tl, mid), query(2*node+1, l, r, mid+1, tr));
    }
} segsum;


int GetBestPosition(int n, int c, int r, int *v, int *s, int *e) {
    seg.build(1, 1, n);
    int res = 0, pos = 0;
    for(int i = 0;i < n;i++){
        seg.update(1, i+1, i+1,1,n, r);
        for(int j = 0;j < i;j++){
            seg.update(1, j+1,j+1, 1, n, v[j]);
        }
        for(int j = i;j < n-1;j++){
            seg.update(1, j+2,j+2,1,n, v[j]);
        }
        segsum.update(1,1,n,1,n,1);
        int ansat = 0;
        for(int j = 0;j < c;j++){
            int lt = s[j]+1;
            int rt = e[j]+1;
            int bl = 1, br = n;
            int ansl = 0;
            while(bl <= br){
                int mid = (bl+br)/2;
                if(segsum.query(1, 1, mid, 1, n) < lt){
                    ansl = mid;
                    bl = mid+1;
                }
                else{
                    br = mid-1;
                }
            }
            ansl++;
            bl = 1, br = n;
            int ansr = n;
            while(bl <= br){
                int mid = (bl+br)/2;
                if(segsum.query(1, 1, mid, 1, n) > rt){
                    br = mid-1;
                }
                else{
                    ansr = mid;
                    bl = mid+1;
                }
            }
            auto [p, t] = seg.query(1, ansl, ansr, 1, n);
            if(p == r) ansat++;
            segsum.update(1, ansl, t-1, 1, n, 0);
            segsum.update(1, t+1, ansr, 1, n, 0);
        }
        if(ansat > res){
            pos = i;
            res = ansat;
        }
    }
    return pos;
}

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