oj.uz

Submission #960116

# Submission time Handle Problem Language Result Execution time Memory
960116 2024-04-09T16:51:35 Z 8pete8 Teams (IOI15_teams) C++17
34 / 100
 4000 ms 63692 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,cursum[mxn+10];
void init(int N, int A[], int B[]){
	vector<pii>v;
	n=N;
	root=400;
	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(cursum==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){
					int g=t[i].qp(pos[i][j]);
					cursum[i]-=g;
					need-=g;
					if(g)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;
				cursum[i]-=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){
						int g=t[i].qp(pos[i][j]);
						need-=g;
						cursum[i]-=g;
						if(g)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;
		cursum[i]=block[i].size();
		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: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:189:8: warning: declaration of 'l' shadows a previous local [-Wshadow]
  189 |    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:189:12: warning: declaration of 'r' shadows a previous local [-Wshadow]
  189 |    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: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:226:26: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  226 |   cursum[i]=block[i].size();
      |             ~~~~~~~~~~~~~^~
teams.cpp:231:6: warning: unused variable 'cnt' [-Wunused-variable]
  231 |  int cnt=0;
      |      ^~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25432 KB Output is correct
2 Correct 6 ms 25436 KB Output is correct
3 Correct 7 ms 25436 KB Output is correct
4 Correct 6 ms 25436 KB Output is correct
5 Correct 7 ms 25436 KB Output is correct
6 Correct 6 ms 25692 KB Output is correct
7 Correct 6 ms 25528 KB Output is correct
8 Correct 6 ms 25436 KB Output is correct
9 Correct 7 ms 25436 KB Output is correct
10 Correct 6 ms 25436 KB Output is correct
11 Correct 6 ms 25612 KB Output is correct
12 Correct 8 ms 25668 KB Output is correct
13 Correct 9 ms 25436 KB Output is correct
14 Correct 7 ms 25620 KB Output is correct
15 Correct 7 ms 25604 KB Output is correct
16 Correct 6 ms 25432 KB Output is correct
17 Correct 6 ms 25436 KB Output is correct
18 Correct 6 ms 25488 KB Output is correct
19 Correct 6 ms 25432 KB Output is correct
20 Correct 6 ms 25652 KB Output is correct
21 Correct 6 ms 25436 KB Output is correct
22 Correct 6 ms 25436 KB Output is correct
23 Correct 6 ms 25436 KB Output is correct
24 Correct 6 ms 25432 KB Output is correct
25 Correct 7 ms 25436 KB Output is correct
26 Correct 6 ms 25436 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 33060 KB Output is correct
2 Correct 28 ms 33232 KB Output is correct
3 Correct 29 ms 33224 KB Output is correct
4 Correct 34 ms 33724 KB Output is correct
5 Correct 28 ms 33232 KB Output is correct
6 Correct 25 ms 33232 KB Output is correct
7 Correct 26 ms 33488 KB Output is correct
8 Correct 23 ms 33228 KB Output is correct
9 Correct 627 ms 33232 KB Output is correct
10 Correct 127 ms 33232 KB Output is correct
11 Correct 43 ms 33228 KB Output is correct
12 Correct 22 ms 33228 KB Output is correct
13 Correct 27 ms 33228 KB Output is correct
14 Correct 25 ms 33232 KB Output is correct
15 Correct 28 ms 33228 KB Output is correct
16 Correct 31 ms 33228 KB Output is correct
17 Correct 24 ms 33232 KB Output is correct
18 Correct 27 ms 33220 KB Output is correct

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 33228 KB Output is correct
2 Correct 37 ms 33216 KB Output is correct
3 Execution timed out 4054 ms 35312 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 63580 KB Output is correct
2 Correct 159 ms 63432 KB Output is correct
3 Execution timed out 4030 ms 63692 KB Time limit exceeded
4 Halted 0 ms 0 KB -