oj.uz

Submission #91750

# Submission time Handle Problem Language Result Execution time Memory
91750 2018-12-29T20:14:42 Z KLPP Teams (IOI15_teams) C++14
77 / 100
 2275 ms 525312 KB 
#include "teams.h"
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
typedef long long int lld;
typedef pair<lld,lld> pll;
#define MAXN 1000000
#define SQ 1000000000000
#define DEBUG 0
/*
4
2 4
1 2
2 3
2 3
2
2 1 3
2 1 1

*/
struct ST
{
    ST *L,*R;
    vector<lld> v;
    lld l,r;
};
typedef ST *tree;
void ext(tree n)
{
    if(!n->L)
    {
        n->L=new ST();
        n->R=new ST();
        lld mid=(n->l+n->r)/2;
        n->L->l=n->l;
        n->L->r=mid;
        n->R->l=mid+1;
        n->R->r=n->r;
    }
}
void upd(tree n,lld pos, lld val)
{
    //cout<<n->l<<" "<<n->r<<endl;
    if(pos<n->l || n->r<pos)return;
    //cout<<n->l<<" "<<n->r<<endl;
    n->v.push_back(val);
    if(n->l==n->r)return;
    ext(n);
    upd(n->L,pos,val);
    upd(n->R,pos,val);
}
int Q(tree n,lld l, lld r, int e)
{
    if(!n)return 0;
    if(r<n->l || n->r<l)return 0;
    if(l<=n->l && n->r<=r){
        int lo,hi;
        lo=-1;
        hi=n->v.size();
        while(hi-lo>1){
            int mid=(lo+hi)/2;
            if(n->v[mid]>e)hi=mid;
            else lo=mid;
        }
        //cout<<hi<<" "<<e<<endl;
        return hi;
    }
    return Q(n->L,l,r,e)+Q(n->R,l,r,e);
}

int query(tree n,lld l, lld r, int s, int e){
    return Q(n,l,r,e)-Q(n,l,r,s-1);
}
lld nav(tree n, int s, int e, int val){
    ext(n);
    //cout<<n->l<<" "<<n->r<<" "<<val<<endl;
    if(n->l==n->r){
        if(val>0)return n->r+1;
        return n->r;
    }
    if(!n->L){
        return n->r+1;
    }
    int ans=query(n->L,n->L->l,n->L->r,s,e);
    //cout<<ans<<endl;
    if(ans>val){
        return nav(n->L,s,e,val);
    }
    return nav(n->R,s,e,val-ans);


}
pair<lld,lld> arr[1000000];

int n;
tree T;
void init(int N, int A[], int B[])
{
    n=N;
    for(int i=0; i<n; i++)
    {
        arr[i]=pll(A[i],B[i]);

    }
    sort(arr,arr+n);
    T=new ST();
    T->l=0;
    T->r=SQ;
    //cout<<T->r<<endl;
    //S->print(0,n,1);
    //cout<<S->q(2,4,2,3);
    for(int i=0; i<n; i++)
    {
        //cout<<arr[i].second<<endl;
        if(DEBUG==0){
                arr[i].second=arr[i].second*MAXN+i+30;
        }
        //cout<<arr[i].second<<" "<<i<<endl;
        upd(T,arr[i].second,i);
    }
    //cout<<nav(T,0,2,3)<<endl;
}

int can(int M, int K[])
{
    sort(K,K+M);
    if(DEBUG==1){
        int pnt=0;
        priority_queue<int>pq;
        for(int i=0;i<M;i++){
            while(pnt<n && arr[pnt].first<=K[i]){
                pq.push(-arr[pnt].second);
                pnt++;
            }
            while(-pq.top()<K[i]){
                if(pq.empty())return 0;
                pq.pop();
            }
            for(int j=0;j<K[i];j++){
                if(pq.empty())return 0;
                pq.pop();
            }
        }return 1;
    }
    stack<pll>s;
    for(int i=0;i<M;i++){
        int lo,hi;
        lo=-1;
        hi=n;
        while(hi-lo>1){
            int mid=(hi+lo)/2;
            if(arr[mid].first<=K[i]){
                lo=mid;
            }else hi=mid;
        }
        //cout<<lo<<endl;
        //cout<<arr[hi].second/MAXN<<endl;
        lld H=MAXN*(lld)K[i];
        while(!s.empty() && s.top().second<=H){
            s.pop();
        }
        int Group=K[i];

        //cout<<H<<endl;
        //cout<<H<<" B"<<s.size()<<endl;
        while(!s.empty() && query(T,H,s.top().second-1,s.top().first+1,lo)<=Group){
            Group-=query(T,H,s.top().second-1,s.top().first+1,lo);
            H=s.top().second;
            s.pop();
        }
        //cout<<s.size()<<" A "<<H<<endl;

        if(s.empty()){
            //cout<<Q(T,0,SQ,lo)<<"Q"<<endl;
            if(query(T,H,SQ,0,lo)<Group){
                return 0;
            }
            H=nav(T,0,lo,Group+query(T,0,H-1,0,lo));
        }else{
            H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
        }

        s.push(pll(lo,H));
        //cout<<lo<<" "<<H<<endl;
    }
    return 1;

}

Compilation message

teams.cpp: In function 'int Q(tree, lld, lld, int)':
teams.cpp:59:21: warning: conversion to 'int' from 'std::vector<long long int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
         hi=n->v.size();
            ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:132:25: warning: conversion to 'std::priority_queue<int>::value_type {aka int}' from 'long long int' may alter its value [-Wconversion]
                 pq.push(-arr[pnt].second);
                         ^~~~~~~~~~~~~~~~
teams.cpp:166:69: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
         while(!s.empty() && query(T,H,s.top().second-1,s.top().first+1,lo)<=Group){
                                                        ~~~~~~~~~~~~~^~
teams.cpp:167:60: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             Group-=query(T,H,s.top().second-1,s.top().first+1,lo);
                                               ~~~~~~~~~~~~~^~
teams.cpp:180:73: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
                                                            ~~~~~~~~~~~~~^~
teams.cpp:180:34: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
             H=nav(T,s.top().first+1,lo,Group+query(T,0,H-1,s.top().first+1,lo));
                     ~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 608 ms 315204 KB Output is correct
2 Correct 618 ms 315000 KB Output is correct
3 Correct 565 ms 315048 KB Output is correct
4 Correct 574 ms 315716 KB Output is correct
5 Correct 132 ms 59764 KB Output is correct
6 Correct 131 ms 60024 KB Output is correct
7 Correct 128 ms 59684 KB Output is correct
8 Correct 131 ms 59844 KB Output is correct
9 Correct 442 ms 57484 KB Output is correct
10 Correct 377 ms 55340 KB Output is correct
11 Correct 159 ms 53140 KB Output is correct
12 Correct 136 ms 53516 KB Output is correct
13 Correct 170 ms 79872 KB Output is correct
14 Correct 275 ms 141876 KB Output is correct
15 Correct 640 ms 270544 KB Output is correct
16 Correct 491 ms 270404 KB Output is correct
17 Correct 131 ms 64168 KB Output is correct
18 Correct 133 ms 63660 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 316100 KB Output is correct
2 Correct 670 ms 316088 KB Output is correct
3 Correct 2275 ms 321552 KB Output is correct
4 Correct 602 ms 315800 KB Output is correct
5 Correct 526 ms 60548 KB Output is correct
6 Correct 478 ms 60404 KB Output is correct
7 Correct 141 ms 60404 KB Output is correct
8 Correct 391 ms 60404 KB Output is correct
9 Correct 448 ms 57680 KB Output is correct
10 Correct 1407 ms 60592 KB Output is correct
11 Correct 1496 ms 60756 KB Output is correct
12 Correct 1895 ms 61436 KB Output is correct
13 Correct 2258 ms 88480 KB Output is correct
14 Correct 2168 ms 291552 KB Output is correct
15 Correct 1154 ms 271476 KB Output is correct
16 Correct 1117 ms 271232 KB Output is correct
17 Correct 824 ms 65448 KB Output is correct
18 Correct 919 ms 65416 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1022 ms 525312 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -