oj.uz

Submission #22033

# Submission time Handle Problem Language Result Execution time Memory
22033 2017-04-28T22:29:23 Z sbansalcs Teams (IOI15_teams) C++14
100 / 100
 2025 ms 390328 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;

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)  {
                val[idx]+=v;
                return v;
            }
            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
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 37200 KB Output is correct
2 Correct 0 ms 37200 KB Output is correct
3 Correct 0 ms 37200 KB Output is correct
4 Correct 0 ms 37200 KB Output is correct
5 Correct 0 ms 37200 KB Output is correct
6 Correct 0 ms 37348 KB Output is correct
7 Correct 0 ms 37200 KB Output is correct
8 Correct 0 ms 37200 KB Output is correct
9 Correct 0 ms 37200 KB Output is correct
10 Correct 0 ms 37200 KB Output is correct
11 Correct 0 ms 37200 KB Output is correct
12 Correct 0 ms 37200 KB Output is correct
13 Correct 0 ms 37200 KB Output is correct
14 Correct 0 ms 37200 KB Output is correct
15 Correct 0 ms 37200 KB Output is correct
16 Correct 0 ms 37200 KB Output is correct
17 Correct 0 ms 37200 KB Output is correct
18 Correct 0 ms 37200 KB Output is correct
19 Correct 0 ms 37200 KB Output is correct
20 Correct 0 ms 37200 KB Output is correct
21 Correct 0 ms 37200 KB Output is correct
22 Correct 0 ms 37200 KB Output is correct
23 Correct 0 ms 37200 KB Output is correct
24 Correct 0 ms 37200 KB Output is correct
25 Correct 0 ms 37200 KB Output is correct
26 Correct 0 ms 37200 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 100600 KB Output is correct
2 Correct 136 ms 100600 KB Output is correct
3 Correct 146 ms 100600 KB Output is correct
4 Correct 146 ms 100600 KB Output is correct
5 Correct 69 ms 100600 KB Output is correct
6 Correct 69 ms 100600 KB Output is correct
7 Correct 83 ms 100600 KB Output is correct
8 Correct 79 ms 100600 KB Output is correct
9 Correct 79 ms 98356 KB Output is correct
10 Correct 79 ms 98356 KB Output is correct
11 Correct 76 ms 101524 KB Output is correct
12 Correct 69 ms 98356 KB Output is correct
13 Correct 93 ms 101392 KB Output is correct
14 Correct 83 ms 99148 KB Output is correct
15 Correct 116 ms 100468 KB Output is correct
16 Correct 133 ms 100600 KB Output is correct
17 Correct 73 ms 101392 KB Output is correct
18 Correct 56 ms 101392 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 100600 KB Output is correct
2 Correct 136 ms 100600 KB Output is correct
3 Correct 493 ms 102608 KB Output is correct
4 Correct 123 ms 100600 KB Output is correct
5 Correct 126 ms 100600 KB Output is correct
6 Correct 129 ms 100600 KB Output is correct
7 Correct 83 ms 100600 KB Output is correct
8 Correct 133 ms 100600 KB Output is correct
9 Correct 99 ms 98356 KB Output is correct
10 Correct 113 ms 98356 KB Output is correct
11 Correct 116 ms 101524 KB Output is correct
12 Correct 143 ms 98356 KB Output is correct
13 Correct 289 ms 101392 KB Output is correct
14 Correct 519 ms 101024 KB Output is correct
15 Correct 143 ms 100468 KB Output is correct
16 Correct 153 ms 100600 KB Output is correct
17 Correct 129 ms 101392 KB Output is correct
18 Correct 133 ms 101524 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 388224 KB Output is correct
2 Correct 889 ms 388224 KB Output is correct
3 Correct 2013 ms 390328 KB Output is correct
4 Correct 926 ms 388224 KB Output is correct
5 Correct 559 ms 388224 KB Output is correct
6 Correct 506 ms 388224 KB Output is correct
7 Correct 436 ms 388224 KB Output is correct
8 Correct 519 ms 388224 KB Output is correct
9 Correct 473 ms 373308 KB Output is correct
10 Correct 489 ms 389016 KB Output is correct
11 Correct 496 ms 389016 KB Output is correct
12 Correct 636 ms 389016 KB Output is correct
13 Correct 1216 ms 388884 KB Output is correct
14 Correct 2025 ms 386376 KB Output is correct
15 Correct 823 ms 388488 KB Output is correct
16 Correct 833 ms 388488 KB Output is correct
17 Correct 543 ms 389016 KB Output is correct
18 Correct 563 ms 389016 KB Output is correct