oj.uz

Submission #671047

# Submission time Handle Problem Language Result Execution time Memory
671047 2022-12-11T17:37:26 Z alvingogo Teams (IOI15_teams) C++14
100 / 100
 1182 ms 232824 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;

struct ST{
	struct no{
		int lch=-1,rch=-1,val=0;
	};
	vector<no> st;
	int newe(no x){
		st.push_back(x);
		return st.size()-1;
	}
	void pull(int x){
		st[x].val=st[st[x].lch].val+st[st[x].rch].val;
	}
	int build(int L,int R){
		if(L==R){
			int x=newe({-1,-1,0});
			return x;
		}
		int m=(L+R)/2;
		int a=build(L,m);
		int b=build(m+1,R);
		int x=newe({a,b,0});
		return x;
	}
	int update(int v,int L,int R,int p){
		if(L==R){
			int x=newe(st[v]);
			st[x].val++;
			return x;
		}
		int m=(L+R)/2;
		if(p<=m){
			int a=update(st[v].lch,L,m,p);
			int x=newe(st[v]);
			st[x].lch=a;
			pull(x);
			return x;
		}
		else{
			int b=update(st[v].rch,m+1,R,p);
			int x=newe(st[v]);
			st[x].rch=b;
			pull(x);
			return x;
		}
	}
	int query(int v,int L,int R,int l,int r){
		if(L==l && r==R){
			return st[v].val;
		}
		int m=(L+R)/2;
		if(r<=m){
			return query(st[v].lch,L,m,l,r);
		}
		else if(l>m){
			return query(st[v].rch,m+1,R,l,r);
		}
		else{
			return query(st[v].lch,L,m,l,m)+query(st[v].rch,m+1,R,m+1,r);
		}
	}
	int bs(int v1,int v2,int L,int R,int k){
		if(L==R){
			return L;
		}
		int s=st[st[v2].lch].val-st[st[v1].lch].val;
		int m=(L+R)/2;
		if(s>=k){
			return bs(st[v1].lch,st[v2].lch,L,m,k);
		}
		else{
			return bs(st[v1].rch,st[v2].rch,m+1,R,k-s);
		}
	}
}st;

int n;
vector<int> rt;
int get(int l,int r,int u,int d){
	if(l>r || u>d){
		return 0;
	}
	return st.query(rt[r],0,n,u,d)-(l==0?0:st.query(rt[l-1],0,n,u,d));
}

vector<int> lis;
void init(int N,int a[],int b[]){
	n=N;
	lis.clear();
	vector<pair<int,int> > c;
	for(int i=0;i<n;i++){
		c.push_back({b[i],a[i]});
	}
	sort(c.begin(),c.end());
	for(int i=0;i<n;i++){
		lis.push_back(c[i].fs);
		c[i].fs=i;
	}
	vector<vector<int> > d(n+1);
	for(int i=0;i<n;i++){
		d[c[i].sc].push_back(c[i].fs);
	}
	rt.resize(n+1);
	rt[0]=st.build(0,n);
	for(int i=1;i<=n;i++){
		rt[i]=rt[i-1];
		for(auto h:d[i]){
			rt[i]=st.update(rt[i],0,n,h);
		}
	}
}
struct DQ{
	int id,mx,sum;
};
int can(int m,int k[]){
	sort(k,k+m);
	vector<DQ> v;
	v.push_back({0,n,0});
	int uu=0;
	for(int i=0;i<m;i++){
		if(i<m-1 && k[i]==k[i+1]){
			uu+=k[i];
			continue;
		}
		int a=k[i];
		k[i]+=uu;
		uu=0;
		int nxt=0;
		int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
		while(v.size()){
			auto h=v.back();
			if(h.mx<lt){
				v.pop_back();
				continue;
			}
			h.sum=max(h.sum,get(h.id+1,a,0,lt));
			int zz=get(h.id+1,a,0,h.mx)-h.sum;
			if(zz<k[i]){
				k[i]-=zz;
				v.pop_back();
				if(v.size()){
					v.back().sum+=h.sum+zz;
				}
			}
			else{
				h.sum+=k[i];
				nxt=st.bs(rt[h.id],rt[a],0,n,h.sum);
				k[i]=0;
				v.back()=h;
				break;
			}
		}
		if(k[i]){
			return 0;
		}
		v.push_back({a,nxt,0});
	}
	return 1;
}

Compilation message

teams.cpp: In member function 'int ST::newe(ST::no)':
teams.cpp:16:19: warning: conversion from 'std::vector<ST::no>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   16 |   return st.size()-1;
      |          ~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:136:58: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  136 |   int lt=lower_bound(lis.begin(),lis.end(),a)-lis.begin()-1;
      |          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 212 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 32124 KB Output is correct
2 Correct 82 ms 32148 KB Output is correct
3 Correct 85 ms 32172 KB Output is correct
4 Correct 83 ms 32120 KB Output is correct
5 Correct 49 ms 30884 KB Output is correct
6 Correct 48 ms 30896 KB Output is correct
7 Correct 48 ms 30900 KB Output is correct
8 Correct 49 ms 30976 KB Output is correct
9 Correct 44 ms 30920 KB Output is correct
10 Correct 44 ms 30764 KB Output is correct
11 Correct 43 ms 30768 KB Output is correct
12 Correct 45 ms 30984 KB Output is correct
13 Correct 52 ms 30980 KB Output is correct
14 Correct 53 ms 31444 KB Output is correct
15 Correct 72 ms 32008 KB Output is correct
16 Correct 75 ms 32076 KB Output is correct
17 Correct 48 ms 30972 KB Output is correct
18 Correct 48 ms 30984 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 32192 KB Output is correct
2 Correct 87 ms 32156 KB Output is correct
3 Correct 233 ms 32208 KB Output is correct
4 Correct 85 ms 32160 KB Output is correct
5 Correct 154 ms 30916 KB Output is correct
6 Correct 136 ms 30908 KB Output is correct
7 Correct 54 ms 30928 KB Output is correct
8 Correct 116 ms 30896 KB Output is correct
9 Correct 44 ms 30976 KB Output is correct
10 Correct 45 ms 30736 KB Output is correct
11 Correct 53 ms 30744 KB Output is correct
12 Correct 149 ms 30872 KB Output is correct
13 Correct 221 ms 31024 KB Output is correct
14 Correct 276 ms 31936 KB Output is correct
15 Correct 111 ms 32048 KB Output is correct
16 Correct 110 ms 32036 KB Output is correct
17 Correct 84 ms 30976 KB Output is correct
18 Correct 79 ms 30896 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 232772 KB Output is correct
2 Correct 626 ms 232796 KB Output is correct
3 Correct 1167 ms 232824 KB Output is correct
4 Correct 619 ms 232820 KB Output is correct
5 Correct 552 ms 226436 KB Output is correct
6 Correct 511 ms 226508 KB Output is correct
7 Correct 283 ms 226424 KB Output is correct
8 Correct 467 ms 226440 KB Output is correct
9 Correct 250 ms 226056 KB Output is correct
10 Correct 276 ms 225824 KB Output is correct
11 Correct 325 ms 225848 KB Output is correct
12 Correct 601 ms 225908 KB Output is correct
13 Correct 833 ms 226992 KB Output is correct
14 Correct 1182 ms 231484 KB Output is correct
15 Correct 563 ms 231456 KB Output is correct
16 Correct 570 ms 231160 KB Output is correct
17 Correct 357 ms 226676 KB Output is correct
18 Correct 348 ms 226548 KB Output is correct