oj.uz

Submission #960114

# Submission time Handle Problem Language Result Execution time Memory
960114 2024-04-09T16:47:51 Z 8pete8 Teams (IOI15_teams) C++17
34 / 100
 4000 ms 67516 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;
      |      ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26716 KB Output is correct
2 Correct 7 ms 26716 KB Output is correct
3 Correct 7 ms 26884 KB Output is correct
4 Correct 7 ms 26716 KB Output is correct
5 Correct 7 ms 26716 KB Output is correct
6 Correct 7 ms 26972 KB Output is correct
7 Correct 7 ms 26716 KB Output is correct
8 Correct 7 ms 26916 KB Output is correct
9 Correct 7 ms 26712 KB Output is correct
10 Correct 6 ms 26716 KB Output is correct
11 Correct 6 ms 26716 KB Output is correct
12 Correct 9 ms 26932 KB Output is correct
13 Correct 9 ms 26716 KB Output is correct
14 Correct 9 ms 26716 KB Output is correct
15 Correct 7 ms 26716 KB Output is correct
16 Correct 7 ms 26896 KB Output is correct
17 Correct 7 ms 26712 KB Output is correct
18 Correct 8 ms 26712 KB Output is correct
19 Correct 7 ms 26712 KB Output is correct
20 Correct 7 ms 26712 KB Output is correct
21 Correct 7 ms 26716 KB Output is correct
22 Correct 7 ms 26912 KB Output is correct
23 Correct 7 ms 26712 KB Output is correct
24 Correct 8 ms 26716 KB Output is correct
25 Correct 6 ms 26716 KB Output is correct
26 Correct 9 ms 26712 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34504 KB Output is correct
2 Correct 30 ms 35268 KB Output is correct
3 Correct 30 ms 35264 KB Output is correct
4 Correct 34 ms 36032 KB Output is correct
5 Correct 35 ms 35016 KB Output is correct
6 Correct 30 ms 35024 KB Output is correct
7 Correct 24 ms 34936 KB Output is correct
8 Correct 24 ms 35024 KB Output is correct
9 Correct 2724 ms 35016 KB Output is correct
10 Correct 1459 ms 35024 KB Output is correct
11 Correct 259 ms 35016 KB Output is correct
12 Correct 41 ms 35012 KB Output is correct
13 Correct 30 ms 35464 KB Output is correct
14 Correct 27 ms 35524 KB Output is correct
15 Correct 33 ms 35528 KB Output is correct
16 Correct 30 ms 35616 KB Output is correct
17 Correct 27 ms 35536 KB Output is correct
18 Correct 27 ms 35536 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 34504 KB Output is correct
2 Correct 37 ms 35680 KB Output is correct
3 Execution timed out 4051 ms 35752 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 63164 KB Output is correct
2 Correct 146 ms 67512 KB Output is correct
3 Execution timed out 4054 ms 67516 KB Time limit exceeded
4 Halted 0 ms 0 KB -