oj.uz

Submission #249603

# Submission time Handle Problem Language Result Execution time Memory
249603 2020-07-15T10:37:23 Z ryansee Teams (IOI15_teams) C++14
77 / 100
 1209 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));
	if(M>=250){
	    /*FOR(i,0,n-1){
		    ll f=lbd(v,pi(A[i],0));
	    	if(f==v.size())continue;
		    ll s=lbd(v,pi(B[i],LLINF));
		    ++ bet[f][s];
    	}*/
    	vector<int>start(n+2,siz(v)),endd(n+2,siz(v));
    	FOR(i,0,siz(v)-1){
    	    FOR(j,i==0?0:v[i-1].f+1,v[i].f)start[j]=i;
    	    FOR(j,i==0?0:v[i-1].f,v[i].f-1)endd[j]=i;
    	}
    	FOR(i,0,n-1){
    	    if(start[A[i]]==siz(v))continue;
    	    ++bet[start[A[i]]][endd[B[i]]];
    	}
	}else{
	    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:14:16: warning: conversion to 'std::vector<int>::value_type {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
 #define siz(x) ll(x.size())
                ^~~~~~~~~~~~
teams.cpp:99:27: note: in expansion of macro 'siz'
      vector<int>start(n+2,siz(v)),endd(n+2,siz(v));
                           ^~~
teams.cpp:14:16: warning: conversion to 'std::vector<int>::value_type {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
 #define siz(x) ll(x.size())
                ^~~~~~~~~~~~
teams.cpp:99:44: note: in expansion of macro 'siz'
      vector<int>start(n+2,siz(v)),endd(n+2,siz(v));
                                            ^~~
teams.cpp:101:50: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
          FOR(j,i==0?0:v[i-1].f+1,v[i].f)start[j]=i;
                                                  ^
teams.cpp:102:49: warning: conversion to '__gnu_cxx::__alloc_traits<std::allocator<int> >::value_type {aka int}' from 'll {aka long long int}' may alter its value [-Wconversion]
          FOR(j,i==0?0:v[i-1].f,v[i].f-1)endd[j]=i;
                                                 ^
teams.cpp:10:11: warning: conversion to 'int' from 'long long int' may alter its value [-Wconversion]
 #define f first
teams.cpp:110:41: 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:110:55: 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:110:55: 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:111:50: 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:111:64: 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:111:64: 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 0 ms 384 KB Output is correct
2 Correct 0 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 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 360 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 0 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 0 ms 384 KB Output is correct
26 Correct 0 ms 384 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 99532 KB Output is correct
2 Correct 174 ms 98764 KB Output is correct
3 Correct 169 ms 98792 KB Output is correct
4 Correct 169 ms 98920 KB Output is correct
5 Correct 113 ms 99148 KB Output is correct
6 Correct 114 ms 98380 KB Output is correct
7 Correct 114 ms 99112 KB Output is correct
8 Correct 117 ms 99148 KB Output is correct
9 Correct 102 ms 99816 KB Output is correct
10 Correct 106 ms 99560 KB Output is correct
11 Correct 106 ms 99560 KB Output is correct
12 Correct 113 ms 99688 KB Output is correct
13 Correct 116 ms 99688 KB Output is correct
14 Correct 116 ms 99432 KB Output is correct
15 Correct 149 ms 98664 KB Output is correct
16 Correct 155 ms 98664 KB Output is correct
17 Correct 107 ms 99944 KB Output is correct
18 Correct 107 ms 99944 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 100292 KB Output is correct
2 Correct 286 ms 100268 KB Output is correct
3 Correct 326 ms 101188 KB Output is correct
4 Correct 173 ms 98956 KB Output is correct
5 Correct 390 ms 99908 KB Output is correct
6 Correct 422 ms 100168 KB Output is correct
7 Correct 377 ms 99912 KB Output is correct
8 Correct 418 ms 100076 KB Output is correct
9 Correct 106 ms 99816 KB Output is correct
10 Correct 114 ms 99560 KB Output is correct
11 Correct 156 ms 99688 KB Output is correct
12 Correct 1209 ms 99816 KB Output is correct
13 Correct 494 ms 99944 KB Output is correct
14 Correct 327 ms 99908 KB Output is correct
15 Correct 263 ms 98792 KB Output is correct
16 Correct 272 ms 98792 KB Output is correct
17 Correct 281 ms 100072 KB Output is correct
18 Correct 247 ms 100200 KB Output is correct

Subtask #4
0 / 23.0

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