Submission #1085192

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085192		yeediot	Teams (IOI15_teams)	C++17	0 / 100	285 ms	149948 KiB

teams

#include<bits/stdc++.h>
#include "teams.h"
using namespace std;
#define ll long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
const int mxn = 5e5 + 5;
int cnt, rt[mxn];
struct segtree{
    struct nde{
        int l, r, c;
    }seg[mxn << 5];
    #define x seg[node]
    int build(int l, int r){
        int node = ++cnt;
        seg[node].c = 0;
        if(l == r){
            return node;
        }
        int mm = l + r >> 1;
        x.l = build(l, mm), x.r = build(mm + 1, r);
        return node;
    }
    int ins(int from, int l, int r, int p){
        int node = ++cnt;
        seg[node] = seg[from];
        if(l == r){
            seg[node].c++;
            return node;
        }
        int mm = l + r >> 1;
        if(p <= mm){
            x.l = ins(x.l, l, mm, p);
        }
        else{
            x.r = ins(x.r, mm + 1, r, p);
        }
        x.c = seg[x.l].c + seg[x.r].c;
        return node;
    }
    int kth(int v, int u, int l, int r, int k){
        if(l == r){
            return l;
        }
        int mm = l + r >> 1;
        int cc = seg[seg[v].r].c - seg[seg[u].r].c;
        if(k > cc){
            return kth(seg[v].l, seg[u].l, l, mm, k - cc);
        }
        else{
            return kth(seg[v].r, seg[u].r, mm + 1, r, k);
        }
    }
    int bs(int v, int u, int l, int r, int k){
        if(l == r){
            return seg[v].c - seg[u].c;
        }
        int mm = l + r >> 1;
        if(k > mm){
            return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c; 
        }
        else{
            return bs(seg[v].r, seg[u].r, mm + 1, r, k);
        }
    }
}tr;
int n;
void init(int N, int a[], int b[]){
    n = N;
    rt[0] = tr.build(1, n);
    vector<pii>pt;
    for(int i = 0; i < n; i++){
        pt.pb({a[i], b[i]});
    }
    sort(all(pt));
    int pos = 0;
    for(int i = 1; i <= n; i++){
        rt[i] = rt[i - 1];
        for(; pos < n and pt[pos].F == i; pos++){
            tr.ins(rt[i], 1, n, pt[pos].S);
        }
    }
}
int can(int m, int K[]){
    vector<array<int, 3>>st;
    vector<int>k;
    for(int i = 0; i < m; i++) k.pb(K[i]);
    st.pb({0, 0, 0});
    sort(all(k));
    for(auto i : k){
        while(sz(st) and st.back()[1] < i){
            st.pop_back();
        }
        int tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
        if(tot < 0){
            return false;
        }
        int cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
        while(sz(st) and cur > st.back()[1]){
            st.pop_back();
            cur = tr.kth(rt[i], rt[st.back()[0]], 1, n, tot - st.back()[2]);
        }
        st.pb({i, cur, tot});
    }
    return true;
}

Compilation message (stderr)

teams.cpp: In member function 'int segtree::build(int, int)':
teams.cpp:32:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::ins(int, int, int, int)':
teams.cpp:43:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::kth(int, int, int, int, int)':
teams.cpp:57:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mm = l + r >> 1;
      |                  ~~^~~
teams.cpp: In member function 'int segtree::bs(int, int, int, int, int)':
teams.cpp:70:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mm = l + r >> 1;
      |                  ~~^~~

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