| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960117 |
2024-04-09T16:52:54 Z |
8pete8 |
Teams (IOI15_teams) |
C++17 |
|
4000 ms |
65248 KB |
#include "teams.h"
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define double long double
const int mxn=2e5,Mxn=5e5,inf=1e9,minf=-1e9;
int root=200;
int n;
struct seg{
int sz=0;
vector<int>lazy,v;
void init(int k){
v.resize(4*sz,0);
lazy.resize(4*sz,inf);
return;
}
void push(int l,int r,int pos){
if(lazy[pos]==inf)return;
v[pos]=lazy[pos]*(r-l+1);
if(l!=r){
lazy[pos*2]=lazy[pos];
lazy[pos*2+1]=lazy[pos];
}
lazy[pos]=inf;
}
void updatepos(int l,int r,int pos,int qpos,int val){
push(l,r,pos);
if(l==r){
v[pos]=val;
return;
}
int mid=l+(r-l)/2;
if(qpos<=mid)updatepos(l,mid,pos*2,qpos,val);
else updatepos(mid+1,r,pos*2+1,qpos,val);
push(l,mid,pos*2);
push(mid+1,r,pos*2+1);
v[pos]=v[pos*2]+v[pos*2+1];
}
int qryrange(int l,int r,int pos,int ql,int qr){
push(l,r,pos);
if(l>qr||r<ql)return 0;
if(ql<=l&&r<=qr)return v[pos];
int mid=l+(r-l)/2;
return qryrange(l,mid,pos*2,ql,qr)+qryrange(mid+1,r,pos*2+1,ql,qr);
}
int qrypos(int l,int r,int pos,int qpos){
push(l,r,pos);
if(l==r)return v[pos];
int mid=l+(r-l)/2;
if(qpos<=mid)return qrypos(l,mid,pos*2,qpos);
else return qrypos(mid+1,r,pos*2+1,qpos);
}
int gets(int l,int r,int pos,int ql,int qr,int val){
push(l,r,pos);
int mid=l+(r-l)/2;
if(l==r)return l;
push(mid+1,r,pos*2+1);
if(v[pos*2+1]>=val)return gets(mid+1,r,pos*2+1,ql,qr,val);
else{
val-=v[pos*2+1];
return gets(l,mid,pos*2,ql,qr,val);
}
}
void updaterange(int l,int r,int pos,int ql,int qr,int val){
push(l,r,pos);
if(l>qr||r<ql)return;
if(ql<=l&&r<=qr){
lazy[pos]=val;
push(l,r,pos);
return;
}
int mid=l+(r-l)/2;
updaterange(l,mid,pos*2,ql,qr,val);
updaterange(mid+1,r,pos*2+1,ql,qr,val);
v[pos]=v[pos*2]+v[pos*2+1];
}
int qr(int l,int r){return qryrange(0,sz,1,l,r);}
int qp(int x){return qrypos(0,sz,1,x);}
int get(int l,int r,int val){return gets(0,sz,1,l,r,val);}
void up(int pos,int x){updatepos(0,sz,1,pos,x);}
void ur(int l,int r,int x){updaterange(0,sz,1,l,r,x);}
}t[mxn+10];
/*
segtree need to:
find the first k element in range l,r(keep sum of cnt)
minus one to all the k
lazy set to clear
update pos and range
*/
bool cmp(pii a,pii b){
if(a.s==b.s)return a.f>b.f;
return a.s<b.s;
}
/*
we can do sqrt decomp keep block (kinda like mo)
each block keep segtree
if block is half valid then we can loop the entire block
there can only be 2 half valid block
else we can do operation on segtree
complexity -> s(sqrt(n))log(n) pls passTT
*/
vector<pii>block[mxn+10];
vector<int>pos[mxn+10];//pos of i block in block2
vector<pair<pii,int>>block2[mxn+10];
int mn[mxn+10],mx[mxn+10],mxall=0,cursum[mxn+10];
void init(int N, int A[], int B[]){
vector<pii>v;
n=N;
root=sqrt(N);
for(int i=0;i<n;i++)v.pb({A[i],B[i]});
sort(all(v),cmp);
for(int i=0;i<n;i++){
mxall=max(mxall,(i/root));
block[i/root].pb({v[i].f,v[i].s});
block2[i/root].pb({{v[i].f,v[i].s},0});
}
for(int i=0;i<=mxall;i++){
if(i)mx[i]=mx[i-1];
if(block[i].empty())continue;
mn[i]=block[i][0].s;
mx[i]=block[i].back().s;
for(int j=0;j<block[i].size();j++)block2[i][j].s=j;
sort(all(block2[i]));
int x=block[i].size();
pos[i].resize(x);
t[i].sz=x-1;
t[i].init(x);
for(int j=0;j<block2[i].size();j++)pos[i][block2[i][j].s]=j;
}
}
int solve(int x){
int need=x;
bool on=0;
int st=inf;
int l=0,r=mxall;
while(l<=r){
int mid=l+(r-l)/2;
if(mx[mid]>=x)r=mid-1,st=min(st,mid);
else l=mid+1;
}
for(int i=st;i<=mxall;i++){
if(block[i].empty())continue;
if(cursum==0)continue;
if(mn[i]<x&&mx[i]>=x){
for(int j=0;j<block[i].size();j++){
if(block[i][j].f<=x&&x<=block[i][j].s){
int g=t[i].qp(pos[i][j]);
cursum[i]-=g;
need-=g;
if(g)t[i].up(pos[i][j],0);
if(need==0)return 1;
}
}
}
else if(mx[i]>=x){
//find the max left bound pos (l<=x)
int l=0,r=block[i].size()-1,ans=minf;
while(l<=r){
int mid=l+(r-l)/2;
if(block2[i][mid].f.f<=x)l=mid+1,ans=max(ans,mid);
else r=mid-1;
}
if(ans==minf)continue;
int sum=t[i].qr(0,ans);
if(sum<=need){
need-=sum;
cursum[i]-=sum;
t[i].ur(0,ans,0);
if(need==0)return 1;
}
else{
for(int j=0;j<block[i].size();j++){
if(block[i][j].f<=x&&x<=block[i][j].s){
int g=t[i].qp(pos[i][j]);
need-=g;
cursum[i]-=g;
if(g)t[i].up(pos[i][j],0);
if(need==0)return 1;
}
}
return 1;
}
}
}
return (!need);
}
int can(int m, int k[]){
vector<int>o;
int sum=0;
for(int i=0;i<m;i++)sum+=k[i];
if(sum>n)return 0;
for(int i=0;i<=mxall;i++){
if(block[i].empty())continue;
cursum[i]=block[i].size();
t[i].ur(0,t[i].sz,1);
}
for(int i=0;i<m;i++)o.pb(k[i]);
sort(all(o));
int cnt=0;
for(auto i:o){
if(solve(i)==0)return 0;
//return 0;
}
return 1;
}/*
int32_t main(){
int n;cin>>n;
int a[n],b[n];
for(int i=0;i<n;i++)cin>>a[i]>>b[i];
init(n,a,b);
int q;cin>>q;
while(q--){
int m;cin>>m;
int k[m];
for(int i=0;i<m;i++)cin>>k[i];
cout<<can(m,k)<<'\n';
}
}*/
/*
we can greedy?
sort all pair(a,b) by b
then for each k 1->m
we can find the first k[i] range that cover k[i]
we can keep doing this?
this will be (s*n) where each m in each qry can be at most n
if this work->we can do sqrt decomp?
*/
Compilation message
teams.cpp: In member function 'void seg::init(int)':
teams.cpp:42:16: warning: unused parameter 'k' [-Wunused-parameter]
42 | void init(int k){
| ~~~~^
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:141:11: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
141 | root=sqrt(N);
| ~~~~^~~
teams.cpp:154:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
154 | for(int j=0;j<block[i].size();j++)block2[i][j].s=j;
| ~^~~~~~~~~~~~~~~~
teams.cpp:156:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
156 | int x=block[i].size();
| ~~~~~~~~~~~~~^~
teams.cpp:160:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int j=0;j<block2[i].size();j++)pos[i][block2[i][j].s]=j;
| ~^~~~~~~~~~~~~~~~~
teams.cpp: In function 'int solve(int)':
teams.cpp:177:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int j=0;j<block[i].size();j++){
| ~^~~~~~~~~~~~~~~~
teams.cpp:189:8: warning: declaration of 'l' shadows a previous local [-Wshadow]
189 | int l=0,r=block[i].size()-1,ans=minf;
| ^
teams.cpp:167:6: note: shadowed declaration is here
167 | int l=0,r=mxall;
| ^
teams.cpp:189:12: warning: declaration of 'r' shadows a previous local [-Wshadow]
189 | int l=0,r=block[i].size()-1,ans=minf;
| ^
teams.cpp:167:10: note: shadowed declaration is here
167 | int l=0,r=mxall;
| ^
teams.cpp:189:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
189 | int l=0,r=block[i].size()-1,ans=minf;
| ~~~~~~~~~~~~~~~^~
teams.cpp:204:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | for(int j=0;j<block[i].size();j++){
| ~^~~~~~~~~~~~~~~~
teams.cpp:165:7: warning: unused variable 'on' [-Wunused-variable]
165 | bool on=0;
| ^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:226:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
226 | cursum[i]=block[i].size();
| ~~~~~~~~~~~~~^~
teams.cpp:231:6: warning: unused variable 'cnt' [-Wunused-variable]
231 | int cnt=0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
25436 KB |
Output is correct |
| 2 |
Runtime error |
25 ms |
51640 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
33740 KB |
Output is correct |
| 2 |
Correct |
28 ms |
33744 KB |
Output is correct |
| 3 |
Correct |
28 ms |
33740 KB |
Output is correct |
| 4 |
Correct |
31 ms |
34240 KB |
Output is correct |
| 5 |
Correct |
27 ms |
33740 KB |
Output is correct |
| 6 |
Correct |
26 ms |
33736 KB |
Output is correct |
| 7 |
Correct |
23 ms |
33744 KB |
Output is correct |
| 8 |
Correct |
23 ms |
33744 KB |
Output is correct |
| 9 |
Correct |
434 ms |
33744 KB |
Output is correct |
| 10 |
Correct |
118 ms |
33744 KB |
Output is correct |
| 11 |
Correct |
38 ms |
33744 KB |
Output is correct |
| 12 |
Correct |
22 ms |
33740 KB |
Output is correct |
| 13 |
Correct |
26 ms |
33740 KB |
Output is correct |
| 14 |
Correct |
25 ms |
33740 KB |
Output is correct |
| 15 |
Correct |
28 ms |
33736 KB |
Output is correct |
| 16 |
Correct |
28 ms |
33740 KB |
Output is correct |
| 17 |
Correct |
24 ms |
33720 KB |
Output is correct |
| 18 |
Correct |
24 ms |
33744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
33740 KB |
Output is correct |
| 2 |
Correct |
38 ms |
33744 KB |
Output is correct |
| 3 |
Execution timed out |
4062 ms |
35892 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
154 ms |
65212 KB |
Output is correct |
| 2 |
Correct |
155 ms |
65248 KB |
Output is correct |
| 3 |
Execution timed out |
4056 ms |
65212 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
