제출 #22031

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
22031		sbansalcs	팀들 (IOI15_teams)	C++14	0 / 100	1859 ms	390332 KiB

teams

#include "teams.h"
#include <stack>
#include <math.h>
#include <vector>
#include <assert.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 5e5+5;
#define right r
#define left l
#define mid (start+end)/2

//struct node2;

void err()  {
    while (1) {
        
    }
}

struct node	{
    node *l,*r;
    int val;
    node()	{
        l=NULL,r=NULL,val=0;
    }
    node* build(int start, int end)	{
        val=0;
        if(start!=end)	{
            l=new node,r=new node,l=l->build(start,mid),r=r->build(mid+1,end);
        }
        return this;
    }
    
    int query(int start, int end, int a, int b)	{
        if(start>=a && end<=b)	return val;
        else if(start>b || end<a)	return 0;
        else	return l->query(start,mid,a,b)+r->query(mid+1,end,a,b);
    }
    
    node* update(int start, int end, int x, int v)	{
        node* f=new node;
        f->left=left;
        f->right=right;
        f->val=val+v;
        if(start==end)	{
            return f;
        }
        else if(x<=mid)	{
            f->left=left->update(start,mid,x,v);
        }
        else	{
            f->right=right->update(mid+1,end,x,v);
        }
        return f;
    }
    
//    int assign(node2* used, int start, int end, int a, int b, int v)    {
////        used=used->lz()
//    }
    
};
node* points[N*4];
int val[N*4];

void build(int idx, int start, int end) {
    points[idx]=NULL;
    val[idx]=0;
    if(start!=end)  {
        build(idx*2, start, mid);
        build(idx*2+1, mid+1, end);
    }
}
void clear(int idx, int start, int end) {
    if(val[idx]!=0 || points[idx]!=NULL)    {
        if(start!=end)  clear(idx*2,start,mid),clear(idx*2+1,mid+1,end);
    }
    val[idx]=0;
    points[idx]=NULL;
}

void lz(int idx,int start, int end) {
    if(points[idx]==NULL)   return;
    val[idx]=points[idx]->val;
    if(start!=end)  {
        points[idx*2]=points[idx]->l;
        points[idx*2+1]=points[idx]->r;
    }
    points[idx]=NULL;
}

//struct node2
//{
//    node* points;
//    int val;
//    node2 *l,*r;
//    node2* build(int start, int end)	{
//        val=0,points=NULL;
//        if(start!=end)	{
//            l=new node2,r=new node2;l=l->build(start,mid),r=r->build(mid+1,end);
//        }
//        return this;
//    }
//    node2* clear(int start, int end)	{
//        if(val!=0 || points!=NULL)	{
//            if(start!=end)	l=l->clear(start,mid),r=r->clear(mid+1,end);
//        }
//        points=NULL,val=0;
//        return this;
//    }
//    node2* lz(int start, int end)	{
//        if(!points) return this;
//        val=points->val;
//        if(start!=end)  {
//            l->points=points->l;
//            r->points=points->r;
//        }
//        points=NULL;
//        return this;
//    }
//};
//
//
//node2* used;

int assign(node* rt, int idx, int start, int end, int a, int b, int v)  {
    if(rt==NULL)    err();
//    if(used==NULL)  err();
//    used=used->lz(start,end);
    lz(idx, start, end);
    if(start>b || end<a)    return 0;
    if(v==0)    return 0;
    int av =rt->val-val[idx];
    
    if(start>=a && end<=b)  {
        if(av<=v)   {
//            used->points=rt;
            points[idx]=rt;
            lz(idx, start, end);
            return av;
        }
        else    {
            if(start==end)  return 0;
            int lf=assign(rt->l, idx*2, start, mid, a, b, v);
            assert(lf<=v);
            int rf=assign(rt->r, idx*2+1, mid+1, end, a, b, v-lf);
            val[idx]=val[idx*2+1]+val[idx*2];
            return rf+lf;
        }
    }
    else    {
        if(start==end)  return 0;

        int lf=assign(rt->l, idx*2, start, mid, a, b, v);
        assert(lf<=v);

        int rf=assign(rt->r, idx*2+1, mid+1, end, a, b, v-lf);
        val[idx]=val[idx*2+1]+val[idx*2];

        return rf+lf;
    }
    
}

node* root[N];
int A[N],B[N];
int n;
int del[N];
int sz=0;
int dp[N];
void init(int _n, int a[], int b[]) {
    
    n=_n;
    vector<pair<int,int>> vt;
    
    for(int i=1;i<=n;i++)	{
        A[i]=a[i-1];
        B[i]=b[i-1];
        vt.push_back({A[i],B[i]});
    }
    sort(vt.begin(),vt.end());
    root[0]=new node;root[0]=root[0]->build(1,n);
    int preve=0;
    for(int i=0;i<n;i++)	{
        while(preve+1<vt[i].first)	{
            root[preve+1]=root[preve];
            preve++;
        }
        root[vt[i].first]=root[preve]->update(1,n,vt[i].second,1);
//        assert(vt[i].first-preve<=1);
        preve=vt[i].first;
    }
    for(int i=preve+1;i<=n;i++)	{
        root[i]=root[i-1];
    }
//    used=new node2;
//    used=used->build(1, n);
    build(1, 1, n);
}
int getCount(int a, int b)	{
    int h=root[b]->query(1,n,b,n)-root[a]->query(1,n,b,n);
    return h;
}
int can(int M, int K[]) {
    sort(K,K+M);
    int sm=0;

    int cnt=0;
//    used=used->clear(1, n);
    clear(1, 1, n);
    for (int i=0; i<M; i++) {
        sm+=K[i];
        cnt=assign(root[K[i]], 1, 1, n, K[i], n, K[i]);
        if(cnt<K[i])    return 0;
        assert(cnt==K[i]);
    }
    assert(sm<=N);
    
    return 1;
}

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