| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960088 |
2024-04-09T15:55:44 Z |
8pete8 |
Teams (IOI15_teams) |
C++17 |
|
4000 ms |
63360 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){
sz=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*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)return void(v[pos]=val);
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);
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;
void init(int N, int A[], int B[]){
vector<pii>v;
n=N;
root=sqrt(N*20LL);
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(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){
need-=t[i].qp(pos[i][j]);
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;
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){
need-=t[i].qp(pos[i][j]);
t[i].up(pos[i][j],0);
if(need==0)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;
t[i].ur(0,t[i].sz,1);
}
for(int i=0;i<m;i++)o.pb(k[i]);
sort(all(o));
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 function 'void init(int, int*, int*)':
teams.cpp:134:11: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
134 | root=sqrt(N*20LL);
| ~~~~^~~~~~~~
teams.cpp:147: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]
147 | for(int j=0;j<block[i].size();j++)block2[i][j].s=j;
| ~^~~~~~~~~~~~~~~~
teams.cpp:149:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
149 | int x=block[i].size();
| ~~~~~~~~~~~~~^~
teams.cpp:153: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]
153 | 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:169: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]
169 | for(int j=0;j<block[i].size();j++){
| ~^~~~~~~~~~~~~~~~
teams.cpp:179:8: warning: declaration of 'l' shadows a previous local [-Wshadow]
179 | int l=0,r=block[i].size()-1,ans=minf;
| ^
teams.cpp:160:6: note: shadowed declaration is here
160 | int l=0,r=mxall;
| ^
teams.cpp:179:12: warning: declaration of 'r' shadows a previous local [-Wshadow]
179 | int l=0,r=block[i].size()-1,ans=minf;
| ^
teams.cpp:160:10: note: shadowed declaration is here
160 | int l=0,r=mxall;
| ^
teams.cpp:179:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
179 | int l=0,r=block[i].size()-1,ans=minf;
| ~~~~~~~~~~~~~~~^~
teams.cpp:193: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]
193 | for(int j=0;j<block[i].size();j++){
| ~^~~~~~~~~~~~~~~~
teams.cpp:158:7: warning: unused variable 'on' [-Wunused-variable]
158 | bool on=0;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
26716 KB |
Output is correct |
| 2 |
Correct |
6 ms |
26716 KB |
Output is correct |
| 3 |
Correct |
7 ms |
26716 KB |
Output is correct |
| 4 |
Correct |
7 ms |
26868 KB |
Output is correct |
| 5 |
Correct |
6 ms |
26884 KB |
Output is correct |
| 6 |
Correct |
7 ms |
26716 KB |
Output is correct |
| 7 |
Correct |
8 ms |
26716 KB |
Output is correct |
| 8 |
Correct |
7 ms |
26716 KB |
Output is correct |
| 9 |
Correct |
6 ms |
26716 KB |
Output is correct |
| 10 |
Correct |
7 ms |
26912 KB |
Output is correct |
| 11 |
Incorrect |
6 ms |
26716 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
34512 KB |
Output is correct |
| 2 |
Correct |
29 ms |
34500 KB |
Output is correct |
| 3 |
Correct |
30 ms |
34512 KB |
Output is correct |
| 4 |
Correct |
32 ms |
34912 KB |
Output is correct |
| 5 |
Correct |
33 ms |
34500 KB |
Output is correct |
| 6 |
Correct |
28 ms |
34508 KB |
Output is correct |
| 7 |
Correct |
23 ms |
34536 KB |
Output is correct |
| 8 |
Correct |
23 ms |
34496 KB |
Output is correct |
| 9 |
Execution timed out |
4035 ms |
34508 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
34500 KB |
Output is correct |
| 2 |
Correct |
36 ms |
34344 KB |
Output is correct |
| 3 |
Execution timed out |
4083 ms |
35144 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
148 ms |
63160 KB |
Output is correct |
| 2 |
Correct |
142 ms |
63356 KB |
Output is correct |
| 3 |
Execution timed out |
4057 ms |
63360 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
