Submission #48987

#	Time	Username	Problem	Language	Result	Execution time	Memory
48987		Namnamseo	팀들 (IOI15_teams)	C++17	0 / 100	3102 ms	142496 KiB

teams

#include <bits/stdc++.h>
#define pb push_back
#define M 524288
using namespace std;

struct r2d{
    vector<int> tree[M*2];
    void put(int x,int y){
        y += M;
        while(y){
            //printf("put %6d\n",y);
            tree[y].pb(x);
            y>>=1;
        }
    }
    inline int get(vector<int>& a,int f,int t){
        if(max(int(upper_bound(a.begin(), a.end(), t) - 
                       lower_bound(a.begin(), a.end(), f)), 0) > 0){
        }
        return max(int(upper_bound(a.begin(), a.end(), t) - 
                       lower_bound(a.begin(), a.end(), f)), 0);
    }
    int rectsum(int l,int r,int d,int u){
        d+=M; u+=M;
        int ret=0;
        while(d<=u){
            if(d&1)    ret+=get(tree[d++], l, r);
            if(!(u&1)) ret+=get(tree[u--], l, r);
            d>>=1; u>>=1;
        }
        return ret;
    }
    int pick_y(int l,int r,int d,int u,int sum_target,int boundary){
        int pos=1, myl=0, myr=M-1, mid;
        sum_target += rectsum(l, r, 0, d-1);
        int making_sum=0;
        while(pos<M){
            mid=(myl+myr)/2;
            pos*=2;
            int cur_sum = get(tree[pos], l, r);
            if(myl<=u && u<=mid) cur_sum += boundary;
            if(making_sum + cur_sum < sum_target){
                myl=mid+1;
                making_sum += cur_sum;
            } else {
                myr=mid;
            }
        }
        return myl;
    }
} seg2d;

int n;
typedef pair<int,int> pp;
vector<pp> pts;

void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0;i<n;++i){
        pts.pb({A[i], B[i]});
    }
    sort(pts.begin(), pts.end());
    for(int i=0; i<n; ++i) seg2d.put(pts[i].first, pts[i].second);
}

typedef pair<pp,int> pyo;
stack<pyo> stk;

int can(int m, int q[])
{
    while(stk.size()) stk.pop();
    stk.push({{0,500000},0});
	sort(q, q+m);
    for(int i=0; i<m; ++i){
        int x=q[i];
        int lasty=x-1;
        int left=x;
        while(true){
            if(stk.size()==0) return false;
            pyo a=stk.top();
            //printf("Querying: %d,%d / %d,%d\n",a.first.first+1, x, lasty+1, a.first.second);
            int that = a.second +
                seg2d.rectsum(a.first.first + 1, x, lasty+1, a.first.second);
            //printf("That's %d\n",that);
            if(that >= left){
                //puts("enough");
                int y = seg2d.pick_y(a.first.first+1, x, lasty+1, a.first.second, left, a.second);
                stk.push({{x, y}, seg2d.rectsum(a.first.first+1, x, lasty+1, y) - left});
                break;
            } else {
                //puts("I'm hungry");
                left -= that;
                lasty = a.first.second;
                stk.pop();
            }
        }
    }
    return true;
}

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