Submission #53926

#	Time	Username	Problem	Language	Result	Execution time	Memory
53926		Benq	Teams (IOI15_teams)	C++14	100 / 100	2773 ms	232764 KiB

teams

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
 
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500001;
 
#include "teams.h"
 
template<int SZ> struct pseg {
    typedef int T;
    static const int LIMIT = 12000000;
    int l[LIMIT], r[LIMIT], nex = 0;
    T val[LIMIT];
    
    //// HELPER
    int copy(int cur) {
        int x = nex++;
        val[x] = val[cur], l[x] = l[cur], r[x] = r[cur];
        return x;
    }
    T comb(T a, T b) { return a+b; }
    void pull(int x) { val[x] = comb(val[l[x]],val[r[x]]); }
 
    //// IMPORTANT
    T query(int cur, int lo, int hi, int L, int R) {  
        if (lo <= L && R <= hi) return val[cur];
        if (R < lo || hi < L) return 0;
        int M = (L+R)/2;
        return comb(query(l[cur],lo,hi,L,M),query(r[cur],lo,hi,M+1,R));
    }
    int upd(int cur, int ind, int v, int L = 0, int R = SZ-1) {
        if (R < ind || ind < L) return cur;
        
        int x = copy(cur);
        if (ind <= L && R <= ind) { val[x] += v; return x; }
        
        int M = (L+R)/2;
        l[x] = upd(l[x],ind,v,L,M), r[x] = upd(r[x],ind,v,M+1,R);
        pull(x); return x;
    }
    int build(int L = 0, int R = SZ-1) {
        int cur = nex++;
        if (L == R) {
            return cur;
        }
        
        int M = (L+R)/2;
        l[cur] = build(L,M), r[cur] = build(M+1,R);
        pull(cur); return cur;
    }
    
    //// PUBLIC
    int loc[SZ];
    T query(int ti, int lo, int hi) { return query(loc[ti],lo,hi,0,SZ-1); }
};
 
pseg<MX> p;
vpi v;
int n;
 
void init(int N, int A[], int B[]) {
    n = N;
    vi nex[MX];
    F0R(i,n) nex[A[i]-1].pb(B[i]);
    p.loc[n] = p.build();
    F0Rd(i,n) {
        p.loc[i] = p.loc[i+1];
        for (int j: nex[i]) p.loc[i] = p.upd(p.loc[i],j,1);
    }
}
 
int dp[200001], m, mx;
vi d, pos;
 
int eval(int w, int x) {
    return dp[w]+p.query(pos[w],0,pos[x]-1)+pos[x];
}
 
int bet(int x, int y) {
    int lo = y, hi = m+1;
    while (lo < hi) {
        int mid = (lo+hi)/2;
        if (eval(x,mid) >= eval(y,mid)) hi = mid;
        else lo = mid+1;
    }
    return lo;
}
 
void pop(int x) {
    while (sz(d) > 1 && bet(d[sz(d)-2],d[sz(d)-1]) <= x) d.pop_back();
}
 
void push(int x) {
    while (sz(d) > 1 && bet(d[sz(d)-2],d[sz(d)-1]) <= bet(d[sz(d)-1],x)) d.pop_back();
    d.pb(x);
}
 
void ad(int x) {
    if (x) {
        pop(x);
        dp[x] = eval(d.back(),x);
    }
    mx = max(mx,dp[x]+p.query(pos[x],0,n));
    push(x);
}
 
int can(int M, int K[]) {
    m = M;
    pos = {0};
    F0R(i,m) pos.pb(K[i]);
    d.clear();
    // cout << "HI " << mx << "\n";
    sort(all(pos));
    mx = 0;
    F0R(i,m+1) ad(i);
    if (mx > n) return 0;
    return 1;
}
 
/*int main() {
    int N; cin >> N;
    int A[N], B[N]; F0R(i,N) cin >> A[i] >> B[i];
    init(N,A,B);
    int Q; cin >> Q;
    F0R(i,Q) {
        int M; cin >> M;
        int K[M]; F0R(j,M) cin >> K[j];
        cout << can(M,K) << "\n";
    }
}*/

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23