oj.uz

답안 #22019

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22019 2017-04-28T21:18:30 Z sbansalcs 팀들 (IOI15_teams) C++14
0 / 100
 979 ms 411664 KB 

#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;



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()
//    }
    
};

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, node2* &used, int start, int end, int a, int b, int v)  {
    used=used->lz(start,end);
    if(start>b || end<a)    return 0;
    if(v==0)    return 0;
    int av =rt->val-used->val;
    
    if(start>=a && end<=b)  {
        if(av<=v)   {
            used->points=rt;
            used=used->lz(start,end);
            return av;
        }
        else    {
            int lf=assign(rt->l, used->l, start, mid, a, b, v);
            int rf=assign(rt->r, used->r, mid+1, end, a, b, v-lf);
            return rf+lf;
        }
    }
    else    {
        int lf=assign(rt->l, used->l, start, mid, a, b, v);
        int rf=assign(rt->r, used->r, mid+1, end, a, b, v-lf);
        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);
}
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 cnt=0;
    used=used->clear(1, n);
    for (int i=0; i<M; i++) {
        cnt=assign(root[K[i]], used, 1, n, K[i], n, K[i]);
        if(cnt<K[i])    return 0;
        assert(cnt==K[i]);
    }
    
    return 1;
}

Compilation message

teams.cpp: In function 'int assign(node*, node2*&, int, int, int, int, int)':
teams.cpp:97:75: warning: declaration of 'used' shadows a global declaration [-Wshadow]
 int assign(node* rt, node2* &used, int start, int end, int a, int b, int v)  {
                                                                           ^
teams.cpp:95:8: note: shadowed declaration is here
 node2* used;
        ^

Subtask #1
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 13780 KB Output is correct
2 Correct 0 ms 13780 KB Output is correct
3 Correct 0 ms 13780 KB Output is correct
4 Correct 0 ms 13780 KB Output is correct
5 Runtime error 0 ms 13780 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 159 ms 86552 KB Output is correct
2 Correct 146 ms 86552 KB Output is correct
3 Correct 143 ms 86552 KB Output is correct
4 Correct 153 ms 86552 KB Output is correct
5 Correct 86 ms 86552 KB Output is correct
6 Correct 79 ms 86552 KB Output is correct
7 Runtime error 89 ms 86552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 146 ms 86552 KB Output is correct
2 Correct 159 ms 86552 KB Output is correct
3 Runtime error 143 ms 86552 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 979 ms 411664 KB Output is correct
2 Correct 816 ms 411664 KB Output is correct
3 Runtime error 829 ms 411664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -