oj.uz

Submission #960115

# Submission time Handle Problem Language Result Execution time Memory
960115 2024-04-09T16:48:38 Z 8pete8 Teams (IOI15_teams) C++17
34 / 100
 4000 ms 63432 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;
	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]);
					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 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: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:187:8: warning: declaration of 'l' shadows a previous local [-Wshadow]
  187 |    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:187:12: warning: declaration of 'r' shadows a previous local [-Wshadow]
  187 |    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:187:29: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  187 |    int l=0,r=block[i].size()-1,ans=minf;
      |              ~~~~~~~~~~~~~~~^~
teams.cpp:201: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]
  201 |     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:225:6: warning: unused variable 'cnt' [-Wunused-variable]
  225 |  int cnt=0;
      |      ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26716 KB Output is correct
2 Correct 8 ms 26716 KB Output is correct
3 Correct 6 ms 26716 KB Output is correct
4 Correct 6 ms 26716 KB Output is correct
5 Correct 7 ms 26712 KB Output is correct
6 Correct 7 ms 26820 KB Output is correct
7 Correct 7 ms 26716 KB Output is correct
8 Correct 8 ms 26716 KB Output is correct
9 Correct 7 ms 26716 KB Output is correct
10 Correct 7 ms 26712 KB Output is correct
11 Correct 6 ms 26904 KB Output is correct
12 Correct 9 ms 26716 KB Output is correct
13 Correct 9 ms 26712 KB Output is correct
14 Correct 7 ms 26968 KB Output is correct
15 Correct 7 ms 26716 KB Output is correct
16 Correct 7 ms 26716 KB Output is correct
17 Correct 7 ms 26716 KB Output is correct
18 Correct 7 ms 26716 KB Output is correct
19 Correct 7 ms 26772 KB Output is correct
20 Correct 6 ms 26716 KB Output is correct
21 Correct 7 ms 26900 KB Output is correct
22 Correct 7 ms 26716 KB Output is correct
23 Correct 6 ms 26716 KB Output is correct
24 Correct 6 ms 26716 KB Output is correct
25 Correct 7 ms 26716 KB Output is correct
26 Correct 6 ms 26716 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 34384 KB Output is correct
2 Correct 29 ms 34512 KB Output is correct
3 Correct 32 ms 34480 KB Output is correct
4 Correct 32 ms 34980 KB Output is correct
5 Correct 34 ms 34512 KB Output is correct
6 Correct 29 ms 34512 KB Output is correct
7 Correct 23 ms 34512 KB Output is correct
8 Correct 23 ms 34456 KB Output is correct
9 Correct 2737 ms 34768 KB Output is correct
10 Correct 1467 ms 34512 KB Output is correct
11 Correct 259 ms 34512 KB Output is correct
12 Correct 41 ms 34512 KB Output is correct
13 Correct 30 ms 34500 KB Output is correct
14 Correct 28 ms 34512 KB Output is correct
15 Correct 32 ms 34508 KB Output is correct
16 Correct 30 ms 34512 KB Output is correct
17 Correct 26 ms 34512 KB Output is correct
18 Correct 26 ms 34332 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 34512 KB Output is correct
2 Correct 36 ms 34512 KB Output is correct
3 Execution timed out 4045 ms 34848 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 63164 KB Output is correct
2 Correct 142 ms 63160 KB Output is correct
3 Execution timed out 4008 ms 63432 KB Time limit exceeded
4 Halted 0 ms 0 KB -