| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 734587 |
2023-05-02T16:45:42 Z |
neki |
Teams (IOI15_teams) |
C++14 |
|
32 ms |
8352 KB |
#include <bits/stdc++.h>
#include "teams.h"
#define vc vector
using namespace std;
const int mn=10;
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[]){
assert(0);
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(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){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());
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
teams.cpp: In function 'void build(int, int, int)':
teams.cpp:19:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for(int i=1;i<pfs[no].size();++i)pfs[no][i]+=pfs[no][i-1];
| ~^~~~~~~~~~~~~~~
teams.cpp:22:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for(int i=0,cpl=0,cpr=0;i<pfs[no].size();++i){
| ~^~~~~~~~~~~~~~~
teams.cpp:23:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
23 | 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:23:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
23 | 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:23:84: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
23 | 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:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | 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:24:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
24 | 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:24:84: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
24 | 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: In function 'int bis(int)':
teams.cpp:47:30: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
47 | int l=0,r=konci[0].size()-1;
| ~~~~~~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
2004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
2004 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
8352 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
