oj.uz

Submission #502144

# Submission time Handle Problem Language Result Execution time Memory
502144 2022-01-05T11:06:06 Z MilosMilutinovic Teams (IOI15_teams) C++14
100 / 100
 3285 ms 155880 KB 
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long

const int N=500050;
const int M=40*N;

//namespace ST{
//	int root,ls[M],rs[M],st[M],tsz;
//	void Set(int&c,int ss,int se,int qs,int qe,int x){
//		if(!c)c=++tsz;
//		if(ss>qe||se<qs)return;
//		if(qs<=ss&&se<=qe){st[c]=x;return;}
//		int mid=ss+se>>1;
//		Set(ls[c],ss,mid,qs,qe,x);
//		Set(rs[c],mid+1,se,qs,qe,x);
//	}
//	int Get(int c,int ss,int se,int qi){
//		if(ss==se)return st[c];
//		int mid=ss+se>>1;
//		if(qi<=mid)return max(st[c],Get(ls[c],ss,mid,qi));
//		else return max(st[c],Get(rs[c],mid+1,se,qi));
//	}
//}

int n,ls[M],rs[M],st[M],root[N],tsz;
void Set(int&c,int p,int ss,int se,int qi,int x){
	c=++tsz;ls[c]=ls[p];rs[c]=rs[p];st[c]=st[p]+x;
	if(ss==se)return;
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ls[p],ss,mid,qi,x);
	else Set(rs[c],rs[p],mid+1,se,qi,x);
}
int Get(int c,int p,int ss,int se,int qs,int qe){
	if(qs>qe||ss>qe||se<qs)return 0;
	if(qs<=ss&&se<=qe)return st[c]-st[p];
	int mid=ss+se>>1;
	return Get(ls[c],ls[p],ss,mid,qs,qe)+Get(rs[c],rs[p],mid+1,se,qs,qe);
}

vector<int> Qs[N];
void init(int N,int A[],int B[]) {
	n=N;
	for(int i=0;i<n;i++)Qs[A[i]].pb(B[i]);
	for(int i=1;i<=n;i++){
		root[i]=root[i-1];
		for(int x:Qs[i])Set(root[i],root[i],1,n,x,1);
	}
}

int cnt[N];
int can(int M,int K[]) {
	ll s=0;
	for(int i=0;i<M;i++)s+=K[i];
	if(s>n)return 0;
	vector<int> val;
	for(int i=0;i<M;i++)val.pb(K[i]),cnt[K[i]]++;
	sort(val.begin(),val.end());
	val.erase(unique(val.begin(),val.end()),val.end());
	int sz=val.size(),nroot=++tsz;
	vector<ll> rem(sz);
	for(int i=0;i<sz;i++){
		int v=val[i];
		ll need=(ll)v*cnt[v];
		for(int j=i;j<sz;j++){
			int nxt=(j==sz-1?n:val[j+1]-1);
			ll x=min(need,Get(root[v],nroot,1,n,val[j],nxt)-rem[j]);
			need-=x; rem[j]+=x;
			if(need==0)break;
			//Set(nroot,1,n,val[j],);
		}
		if(need>0){
			for(int x:val)cnt[x]=0;
			return 0;
		}
	}
	for(int x:val)cnt[x]=0;
	return 1;
}

Compilation message

teams.cpp: In function 'void Set(int&, int, int, int, int, int)':
teams.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'int Get(int, int, int, int, int, int)':
teams.cpp:39:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |  int mid=ss+se>>1;
      |          ~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:44:15: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   44 | void init(int N,int A[],int B[]) {
      |           ~~~~^
teams.cpp:7:11: note: shadowed declaration is here
    7 | const int N=500050;
      |           ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:54:13: warning: declaration of 'M' shadows a global declaration [-Wshadow]
   54 | int can(int M,int K[]) {
      |         ~~~~^
teams.cpp:8:11: note: shadowed declaration is here
    8 | const int M=40*N;
      |           ^
teams.cpp:62:17: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   62 |  int sz=val.size(),nroot=++tsz;
      |         ~~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11980 KB Output is correct
2 Correct 6 ms 11980 KB Output is correct
3 Correct 6 ms 11980 KB Output is correct
4 Correct 6 ms 11980 KB Output is correct
5 Correct 6 ms 11980 KB Output is correct
6 Correct 6 ms 12108 KB Output is correct
7 Correct 6 ms 11980 KB Output is correct
8 Correct 6 ms 11980 KB Output is correct
9 Correct 6 ms 11980 KB Output is correct
10 Correct 6 ms 11980 KB Output is correct
11 Correct 6 ms 11980 KB Output is correct
12 Correct 6 ms 11980 KB Output is correct
13 Correct 6 ms 11980 KB Output is correct
14 Correct 6 ms 12052 KB Output is correct
15 Correct 7 ms 12080 KB Output is correct
16 Correct 6 ms 12056 KB Output is correct
17 Correct 6 ms 11980 KB Output is correct
18 Correct 7 ms 12064 KB Output is correct
19 Correct 6 ms 11980 KB Output is correct
20 Correct 6 ms 12060 KB Output is correct
21 Correct 6 ms 11980 KB Output is correct
22 Correct 6 ms 12060 KB Output is correct
23 Correct 7 ms 11980 KB Output is correct
24 Correct 6 ms 12064 KB Output is correct
25 Correct 6 ms 11980 KB Output is correct
26 Correct 7 ms 12056 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 35820 KB Output is correct
2 Correct 51 ms 35780 KB Output is correct
3 Correct 50 ms 35772 KB Output is correct
4 Correct 54 ms 36788 KB Output is correct
5 Correct 34 ms 34628 KB Output is correct
6 Correct 33 ms 34624 KB Output is correct
7 Correct 33 ms 34632 KB Output is correct
8 Correct 33 ms 34624 KB Output is correct
9 Correct 32 ms 34112 KB Output is correct
10 Correct 33 ms 33788 KB Output is correct
11 Correct 34 ms 34852 KB Output is correct
12 Correct 37 ms 33688 KB Output is correct
13 Correct 37 ms 35068 KB Output is correct
14 Correct 39 ms 34436 KB Output is correct
15 Correct 46 ms 35640 KB Output is correct
16 Correct 45 ms 35652 KB Output is correct
17 Correct 35 ms 34948 KB Output is correct
18 Correct 35 ms 35100 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 36204 KB Output is correct
2 Correct 99 ms 36200 KB Output is correct
3 Correct 139 ms 39532 KB Output is correct
4 Correct 53 ms 36804 KB Output is correct
5 Correct 58 ms 35080 KB Output is correct
6 Correct 53 ms 34976 KB Output is correct
7 Correct 50 ms 35108 KB Output is correct
8 Correct 52 ms 35068 KB Output is correct
9 Correct 34 ms 34084 KB Output is correct
10 Correct 36 ms 34104 KB Output is correct
11 Correct 70 ms 35148 KB Output is correct
12 Correct 1088 ms 34000 KB Output is correct
13 Correct 257 ms 35604 KB Output is correct
14 Correct 181 ms 37756 KB Output is correct
15 Correct 76 ms 36228 KB Output is correct
16 Correct 72 ms 36152 KB Output is correct
17 Correct 59 ms 35388 KB Output is correct
18 Correct 54 ms 35392 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 144996 KB Output is correct
2 Correct 457 ms 145056 KB Output is correct
3 Correct 623 ms 152864 KB Output is correct
4 Correct 341 ms 146108 KB Output is correct
5 Correct 203 ms 139028 KB Output is correct
6 Correct 205 ms 139028 KB Output is correct
7 Correct 188 ms 139024 KB Output is correct
8 Correct 205 ms 138880 KB Output is correct
9 Correct 151 ms 133988 KB Output is correct
10 Correct 157 ms 138420 KB Output is correct
11 Correct 1683 ms 138300 KB Output is correct
12 Correct 3285 ms 138488 KB Output is correct
13 Correct 944 ms 146260 KB Output is correct
14 Correct 715 ms 155880 KB Output is correct
15 Correct 348 ms 150692 KB Output is correct
16 Correct 347 ms 150700 KB Output is correct
17 Correct 212 ms 145148 KB Output is correct
18 Correct 207 ms 145132 KB Output is correct