oj.uz

Submission #249373

# Submission time Handle Problem Language Result Execution time Memory
249373 2020-07-14T18:37:19 Z ryansee Teams (IOI15_teams) C++14
77 / 100
 2715 ms 524292 KB 
#include "teams.h"

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (500006)
const ll sq = 720;
ll n, A[MAXN], B[MAXN];
struct node {
	int s,e,m;
	ll v;
	node *l,*r;
	node(int S,int E,bool prog){
		s=S,e=E,m=(s+e)>>1;
		v=0;
		if(s!=e&&prog){
			l=new node(s,m,1),r=new node(m+1,e,1);
		}else l=r=0;
	}
	node* update(int x,ll nval){
		node* tmp=new node(s,e,0);
		if(s==e){
			tmp->v=v+nval;
			return tmp;
		}
		if(x>m){
			tmp->l=l;
			tmp->r=r->update(x,nval);
		}else{
			tmp->l=l->update(x,nval);
			tmp->r=r;
		}
		tmp->v=tmp->l->v+tmp->r->v;
		return tmp;
	}
	ll rmq(int x,int y){
		if(s==x&&e==y)return v;
		if(x>m)return r->rmq(x,y);
		else if(y<=m)return l->rmq(x,y);
		else return l->rmq(x,m)+r->rmq(m+1,y);
	}
} *seg[MAXN];
void init(int N, int _A[], int _B[]) {
	n=N;
	FOR(i,0,n-1)A[i]=_A[i],B[i]=_B[i];
	vector<pi> v;
	FOR(i,0,n-1)v.eb(A[i],B[i]);
	sort(all(v),greater<>());
	seg[0]=new node(0,n+1,1);
	FOR(i,1,n){
		seg[i]=seg[i-1];
		while(v.size()&&v.back().f==i){
			seg[i]=seg[i]->update(v.back().s,1);
			v.pop_back();
		}
	}
}
int can(int M, int K[]) {
	if(accumulate(K,K+M,0ll)>n) return 0;
	sort(K,K+M);
	vector<pi> v;
	FOR(i,0,M-1){
		if(v.empty()||v.back().f!=K[i])v.eb(K[i],1);
		else ++v.back().s;
	}
	assert(v.size() <= 2 * sq + 3);
	vector<vector<ll>> bet(siz(v), vector<ll>(siz(v)+1, 0));
	FOR(i,0,siz(v)-1)FOR(j,i+1,siz(v)){
		bet[i][j]=seg[v[i].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
		if(i) bet[i][j]-=seg[v[i-1].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
	}
	vector<ll> cnt(siz(v)+1,0);
	FOR(i,0,siz(v)-1){
		FOR(j,i+1,siz(v))cnt[j]+=bet[i][j];
		ll need=v[i].f*v[i].s,sum=0;
		FOR(j,i+1,siz(v)){
			if(cnt[j]+sum>=need){
				cnt[j]-=need-sum, sum=need;
				break;
			}else{
				sum+=cnt[j],cnt[j]=0;
			}
		}
		if(sum^need) return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:73:21: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
  seg[0]=new node(0,n+1,1);
                    ~^~
teams.cpp:11:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define s second
           ^
teams.cpp:77:35: note: in expansion of macro 's'
    seg[i]=seg[i]->update(v.back().s,1);
                                   ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:10:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define f first
teams.cpp:93:37: note: in expansion of macro 'f'
   bet[i][j]=seg[v[i].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
                                     ^
teams.cpp:93:51: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   bet[i][j]=seg[v[i].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
                                       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:93:51: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
teams.cpp:10:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define f first
teams.cpp:94:46: note: in expansion of macro 'f'
   if(i) bet[i][j]-=seg[v[i-1].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
                                              ^
teams.cpp:94:60: warning: conversion to 'int' from 'll {aka long long int}' may alter its value [-Wconversion]
   if(i) bet[i][j]-=seg[v[i-1].f]->rmq(v[j-1].f,j == siz(v) ? n+1 : (v[j].f-1));
                                                ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
teams.cpp:94:60: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 98636 KB Output is correct
2 Correct 165 ms 98668 KB Output is correct
3 Correct 173 ms 98664 KB Output is correct
4 Correct 174 ms 98920 KB Output is correct
5 Correct 127 ms 98380 KB Output is correct
6 Correct 121 ms 98280 KB Output is correct
7 Correct 124 ms 98380 KB Output is correct
8 Correct 123 ms 98508 KB Output is correct
9 Correct 104 ms 99816 KB Output is correct
10 Correct 103 ms 99560 KB Output is correct
11 Correct 102 ms 99588 KB Output is correct
12 Correct 114 ms 99688 KB Output is correct
13 Correct 120 ms 99816 KB Output is correct
14 Correct 121 ms 99564 KB Output is correct
15 Correct 152 ms 98664 KB Output is correct
16 Correct 157 ms 98792 KB Output is correct
17 Correct 114 ms 99944 KB Output is correct
18 Correct 112 ms 100056 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2715 ms 99012 KB Output is correct
2 Correct 2416 ms 99744 KB Output is correct
3 Correct 300 ms 101188 KB Output is correct
4 Correct 162 ms 98920 KB Output is correct
5 Correct 2651 ms 99252 KB Output is correct
6 Correct 2383 ms 99528 KB Output is correct
7 Correct 2691 ms 99204 KB Output is correct
8 Correct 2428 ms 99104 KB Output is correct
9 Correct 106 ms 99816 KB Output is correct
10 Correct 112 ms 99672 KB Output is correct
11 Correct 133 ms 99688 KB Output is correct
12 Correct 1268 ms 99916 KB Output is correct
13 Correct 513 ms 99996 KB Output is correct
14 Correct 340 ms 99952 KB Output is correct
15 Correct 281 ms 98792 KB Output is correct
16 Correct 278 ms 98792 KB Output is correct
17 Correct 291 ms 100072 KB Output is correct
18 Correct 248 ms 100200 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 1031 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -