Submission #960070

#	Time	Username	Problem	Language	Result	Execution time	Memory
960070		8pete8	Teams (IOI15_teams)	C++17	0 / 100	4040 ms	55480 KiB

teams

#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[800];
/*
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];
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++){
		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<=root;i++){
		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;
	for(int i=0;i<=root;i++){
		if(block[i].empty())continue;
		if(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;
				}
			}
			on=1;
		}
		else if(on){
			//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;
	for(int i=0;i<=root;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 (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:135:11: warning: conversion from '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'} to 'int' may change value [-Wfloat-conversion]
  135 |  root=sqrt(N);
      |       ~~~~^~~
teams.cpp:146: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]
  146 |   for(int j=0;j<block[i].size();j++)block2[i][j].s=j;
      |               ~^~~~~~~~~~~~~~~~
teams.cpp:148:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  148 |   int x=block[i].size();
      |         ~~~~~~~~~~~~~^~
teams.cpp:152: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]
  152 |   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:161: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]
  161 |    for(int j=0;j<block[i].size();j++){
      |                ~^~~~~~~~~~~~~~~~
teams.cpp:172:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  172 |    int l=0,r=block[i].size()-1,ans=minf;
      |              ~~~~~~~~~~~~~~~^~
teams.cpp:186: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]
  186 |     for(int j=0;j<block[i].size();j++){
      |                 ~^~~~~~~~~~~~~~~~

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