oj.uz

Submission #91751

# Submission time Handle Problem Language Result Execution time Memory
91751 2018-12-29T20:17:58 Z KLPP Teams (IOI15_teams) C++14
77 / 100
 2655 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 500000
#define SQ 250001000001
#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[MAXN];

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+1;
        }
        //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 380 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 632 KB Output is correct
4 Correct 1 ms 676 KB Output is correct
5 Correct 2 ms 504 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 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 4 ms 504 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 504 KB Output is correct
17 Correct 5 ms 376 KB Output is correct
18 Correct 4 ms 376 KB Output is correct
19 Correct 3 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 380 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 380 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 304860 KB Output is correct
2 Correct 593 ms 304848 KB Output is correct
3 Correct 539 ms 304720 KB Output is correct
4 Correct 527 ms 305104 KB Output is correct
5 Correct 123 ms 57724 KB Output is correct
6 Correct 125 ms 57708 KB Output is correct
7 Correct 122 ms 57812 KB Output is correct
8 Correct 122 ms 57832 KB Output is correct
9 Correct 405 ms 55980 KB Output is correct
10 Correct 322 ms 53600 KB Output is correct
11 Correct 141 ms 51624 KB Output is correct
12 Correct 120 ms 51816 KB Output is correct
13 Correct 157 ms 77356 KB Output is correct
14 Correct 224 ms 136608 KB Output is correct
15 Correct 488 ms 261324 KB Output is correct
16 Correct 444 ms 261324 KB Output is correct
17 Correct 129 ms 62128 KB Output is correct
18 Correct 124 ms 61812 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 305188 KB Output is correct
2 Correct 576 ms 305336 KB Output is correct
3 Correct 1574 ms 310356 KB Output is correct
4 Correct 532 ms 305232 KB Output is correct
5 Correct 502 ms 58196 KB Output is correct
6 Correct 458 ms 58112 KB Output is correct
7 Correct 137 ms 58284 KB Output is correct
8 Correct 378 ms 58160 KB Output is correct
9 Correct 430 ms 56136 KB Output is correct
10 Correct 1262 ms 59032 KB Output is correct
11 Correct 1361 ms 59304 KB Output is correct
12 Correct 1858 ms 59632 KB Output is correct
13 Correct 2655 ms 84932 KB Output is correct
14 Correct 2258 ms 281804 KB Output is correct
15 Correct 1112 ms 261960 KB Output is correct
16 Correct 1116 ms 261752 KB Output is correct
17 Correct 785 ms 62456 KB Output is correct
18 Correct 848 ms 62560 KB Output is correct

Subtask #4
0 / 23.0

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