Submission #734591

#	Time	Username	Problem	Language	Result	Execution time	Memory
734591		neki	Teams (IOI15_teams)	C++14	0 / 100	1436 ms	524288 KiB

teams

#include <bits/stdc++.h>
#define vc vector

using namespace std;
const int mn=500100;
int n;
vc<int> pfs[4*mn],konci[4*mn],pl[4*mn],pr[4*mn];
void add(int ql,int qr,int l=1,int r=n,int no=0){
    pfs[no].push_back(ql==l);konci[no].push_back(qr);
    if(ql==l)return;
    int mid=(l+r)/2;
    if(qr<=mid)add(ql,qr,l,mid,2*no+1);
    else if(mid+1<=ql)add(ql,qr,mid+1,r,2*no+2);
    else add(ql,qr,l,mid,2*no+1),add(mid+1,qr,mid+1,r,2*no+2);
}
void build(int l=1,int r=n,int no=0){
    for(int i=1;i<pfs[no].size();++i)pfs[no][i]+=pfs[no][i-1];
    if(l==r)return;
    int mid=(l+r)/2;
    for(int i=0,cpl=0,cpr=0;i<pfs[no].size();++i){
        while(cpl+1<konci[2*no+1].size()&&konci[2*no+1][cpl+1]<=konci[no][i])++cpl;pl[no].push_back(cpl);
        while(cpr+1<konci[2*no+2].size()&&konci[2*no+2][cpr+1]<=konci[no][i])++cpr;pr[no].push_back(cpr);
    }
    build(l,mid,2*no+1),build(mid+1,r,2*no+2);
}
void init(int N,int A[],int B[]){
    n=N;
    for(int i=0;i<4*mn;++i)pfs[i].push_back(0),konci[i].push_back(-1);
    vc<pair<int,int>> ints;for(int i=0;i<N;++i)ints.emplace_back(A[i],B[i]);
    sort(ints.begin(),ints.end(),[](pair<int,int> a,pair<int,int>b){return a.second<b.second;});
    for(auto i:ints)add(i.first,i.second);
    build();
}
int countw(int pos,int ql,int qr,int l=1,int r=n,int no=0){
    assert(0<=ql&&0<=qr&&ql<pfs[no].size()&&qr<pfs[no].size());
    assert(l<=pos&&pos<=r);
    int ret=pfs[no][qr]-pfs[no][ql];
    if(l==r)return ret;
    int mid=(l+r)/2;
    if(pos<=mid)return ret+countw(pos,pl[no][ql],pl[no][qr],l,mid,2*no+1);
    else return ret+countw(pos,pr[no][ql],pr[no][qr],mid+1,r,2*no+2);
}
int bis(int pos){
    assert(konci[0][0]<=pos);
    int l=0,r=konci[0].size()-1;
    while(l<r){
        int mid=(l+r+1)/2;
        if(konci[0][mid]<=pos)l=mid;
        else r=mid-1;
    }
    assert(konci[0][l]<=pos);
    return l;
}
int count(int ql,int qr){assert(ql<=qr);return countw(ql,bis(ql-1),bis(qr));}
int can(int m,int K[]){
    vc<int> k(m+1);for(int i=0;i<m;++i)k[i]=K[i];k[m]=n+1;sort(k.begin(),k.end());assert(k[m]==n+1);
    int c=0;
    for(int i=0;i<m;++i){
        int vsi=count(k[i],n);
        if(k[i]+c>vsi)return 0;
        c+=k[i];c-=count(k[i],k[i+1]-1);if(c<0)c=0;
    }
    return c==0;
}

Compilation message (stderr)

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:17:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=1;i<pfs[no].size();++i)pfs[no][i]+=pfs[no][i-1];
      |                 ~^~~~~~~~~~~~~~~
teams.cpp:20:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0,cpl=0,cpr=0;i<pfs[no].size();++i){
      |                             ~^~~~~~~~~~~~~~~
teams.cpp:21:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         while(cpl+1<konci[2*no+1].size()&&konci[2*no+1][cpl+1]<=konci[no][i])++cpl;pl[no].push_back(cpl);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~
teams.cpp:21:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   21 |         while(cpl+1<konci[2*no+1].size()&&konci[2*no+1][cpl+1]<=konci[no][i])++cpl;pl[no].push_back(cpl);
      |         ^~~~~
teams.cpp:21:84: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   21 |         while(cpl+1<konci[2*no+1].size()&&konci[2*no+1][cpl+1]<=konci[no][i])++cpl;pl[no].push_back(cpl);
      |                                                                                    ^~
teams.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         while(cpr+1<konci[2*no+2].size()&&konci[2*no+2][cpr+1]<=konci[no][i])++cpr;pr[no].push_back(cpr);
      |               ~~~~~^~~~~~~~~~~~~~~~~~~~~
teams.cpp:22:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   22 |         while(cpr+1<konci[2*no+2].size()&&konci[2*no+2][cpr+1]<=konci[no][i])++cpr;pr[no].push_back(cpr);
      |         ^~~~~
teams.cpp:22:84: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   22 |         while(cpr+1<konci[2*no+2].size()&&konci[2*no+2][cpr+1]<=konci[no][i])++cpr;pr[no].push_back(cpr);
      |                                                                                    ^~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from teams.cpp:1:
teams.cpp: In function 'int countw(int, int, int, int, int, int)':
teams.cpp:35:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     assert(0<=ql&&0<=qr&&ql<pfs[no].size()&&qr<pfs[no].size());
      |                          ~~^~~~~~~~~~~~~~~
teams.cpp:35:47: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     assert(0<=ql&&0<=qr&&ql<pfs[no].size()&&qr<pfs[no].size());
      |                                             ~~^~~~~~~~~~~~~~~
teams.cpp: In function 'int bis(int)':
teams.cpp:45:30: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   45 |     int l=0,r=konci[0].size()-1;
      |               ~~~~~~~~~~~~~~~^~

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