| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 960112 |
2024-04-09T16:45:57 Z |
8pete8 |
Teams (IOI15_teams) |
C++17 |
|
0 ms |
0 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;
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;
//cout<<x<<"PPPP\n";
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=0;i<=mxall;i++){
if(block[i].empty())continue;
if(t[i].qr(0,t[i].sz)==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){
need-=t[i].qp(pos[i][j]);
//if(t[i].qp(pos[i][j]))cout<<(i*root)+pos[i][j]<<" "<<pos[i][j]<<"G\n";
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);
for(int j=0;j<=ans;j++)if(t[i].qp(pos[i][j]))cout<<(i*root)+pos[i][j]<<" "<<pos[i][j]<<"PP\n";
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]);
//if(t[i].qp(pos[i][j]))cout<<(i*root)+pos[i][j]<<" "<<pos[i][j]<<"GG\n";
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;
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*20LL);
| ~~~~^~~~~~~~
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:178: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]
178 | 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:168:6: note: shadowed declaration is here
168 | 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:168:10: note: shadowed declaration is here
168 | 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:229:6: warning: unused variable 'cnt' [-Wunused-variable]
229 | int cnt=0;
| ^~~
teams.cpp: In function 'int32_t main()':
teams.cpp:237:6: warning: declaration of 'n' shadows a global declaration [-Wshadow]
237 | int n;cin>>n;
| ^
teams.cpp:38:5: note: shadowed declaration is here
38 | int n;
| ^
/usr/bin/ld: /tmp/ccUaKY8m.o: in function `main':
grader.c:(.text.startup+0x0): multiple definition of `main'; /tmp/cc3LlGAl.o:teams.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
