제출 #1085189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1085189		yeediot	팀들 (IOI15_teams)	C++17	0 / 100	2215 ms	524288 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<ll,ll>
#define pb push_back
#define sz(x) (ll)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<ll>
#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 ll mxn = 5e5 + 5;
ll cnt, rt[mxn];
struct segtree{
    struct nde{
        ll l, r;
        ll c;
    }seg[mxn << 5];
    #define x seg[node]
    ll build(ll l, ll r){
        ll node = ++cnt;
        seg[node].c = 0;
        if(l == r){
            return node;
        }
        ll mm = l + r >> 1;
        x.l = build(l, mm), x.r = build(mm + 1, r);
        return node;
    }
    ll ins(ll from, ll l, ll r, ll p){
        ll node = ++cnt;
        seg[node] = seg[from];
        if(l == r){
            seg[node].c++;
            return node;
        }
        ll 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;
    }
    ll kth(ll v, ll u, ll l, ll r, ll k){
        if(l == r){
            return l;
        }
        ll mm = l + r >> 1;
        ll 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);
        }
    }
    ll bs(ll v, ll u, ll l, ll r, ll k){
        if(l == r){
            return seg[v].c - seg[u].c;
        }
        ll mm = l + r >> 1;
        if(k > mm){
            return bs(seg[v].r, seg[u].r, mm + 1, r, k);
        }
        else{
            return bs(seg[v].l, seg[u].l, l, mm, k) + seg[seg[v].r].c - seg[seg[u].r].c; 
        }
    }
}tr;
ll n;
void init(int N, int a[], int b[]){
    n = N;
    rt[0] = tr.build(1, n);
    vector<pair<ll, ll>>pt;
    for(ll i = 0; i < n; i++){
        pt.pb({a[i], b[i]});
    }
    sort(all(pt));
    ll pos = 0;
    for(ll 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<ll, 3>>st;
    vector<ll>k;
    for(ll i = 0; i < m; i++) k.pb(K[i]);
    st.pb({0LL, 0LL, 0LL});
    sort(all(k));
    for(auto i : k){
        while(sz(st) and st.back()[1] < i){
            st.pop_back();
        }
        ll tot = st.back()[2] + tr.bs(rt[i], rt[st.back()[0]], 1, n, i) - i;
        if(tot < 0){
            return false;
        }
        ll 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;
}

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In member function 'long long int segtree::build(long long int, long long int)':
teams.cpp:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |         ll mm = l + r >> 1;
      |                 ~~^~~
teams.cpp: In member function 'long long int segtree::ins(long long int, long long int, long long int, long long int)':
teams.cpp:44:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |         ll mm = l + r >> 1;
      |                 ~~^~~
teams.cpp: In member function 'long long int segtree::kth(long long int, long long int, long long int, long long int, long long int)':
teams.cpp:58:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |         ll mm = l + r >> 1;
      |                 ~~^~~
teams.cpp: In member function 'long long int segtree::bs(long long int, long long int, long long int, long long int, long long int)':
teams.cpp:71:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         ll mm = l + r >> 1;
      |                 ~~^~~

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