Submission #583362

#	Time	Username	Problem	Language	Result	Execution time	Memory
583362		hibiki	Jousting tournament (IOI12_tournament)	C++11	0 / 100	1092 ms	4716 KiB

tournament

#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()

int n,c,r;
int po[100005],fen[100005];
vector<pair<int,int> > v;

struct node
{
    int mx = 0;
    node *l = NULL, *r = NULL;
} *root;

void f_up(int idx,int val)
{
    idx++;
    while(idx < 100005)
    {
        fen[idx] += val;
        idx += idx & -idx;
    }
}

int f_que(int idx)
{
    int ret = 0;
    idx++;
    while(idx > 0)
    {
        ret += fen[idx];
        idx -= idx & -idx;
    }
    return ret;
}

node* build(int l,int r)
{
    node *ptr = new node;
    if(l == r)
    {
        ptr->mx = po[l];
        return ptr;
    }
    int mid = (l + r) / 2;
    ptr->l = build(l,mid);
    ptr->r = build(mid + 1, r);
    ptr->mx = max(ptr->l->mx, ptr->r->mx);
    return ptr;
}

int ll,rr;
int query(node *ptr,int l,int r)
{
    if(ll <= l && r <= rr) return ptr->mx;
    if(r < ll || rr < l) return 0;
    int mid = (l + r) / 2;
    return max(query(ptr->l, l, mid), query(ptr->r, mid + 1, r));
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
    n = N, c = C, r = R;
    for(int i = 0; i < n; i++)
        po[i] = K[i];
    root = build(0, n - 1);
    for(int i = 0; i < c; i++)
    {
        int s = S[i], e = E[i];
        s += f_que(s);
        e += f_que(e);
        f_up(S[i], e - s);
        v.pb({s,e});
    }
    int ans = 0;
    for(int i = 0; i < n; i++)
    {
        int cnt = 0;
        for(int j = 0; j < c; j++)
        {
            int s = v[j].f;
            int e = v[j].s;
            if(s >= i) s--;
            if(e >= i) e--;
            ll = s, rr = e;
            int gt = query(root, 0, n - 1);
            if(s <= i && i <= e)
            {
                if(r > gt) cnt++;
                else break;
            }
        }
        ans = max(ans, cnt);
    }
    return ans;
}

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