oj.uz

Submission #590160

# Submission time Handle Problem Language Result Execution time Memory
590160 2022-07-05T15:22:37 Z FatihSolak Teams (IOI15_teams) C++17
100 / 100
 3196 ms 287276 KB 
#include "teams.h"
#include <bits/stdc++.h>
#define N 500005
#define K 100
using namespace std;
struct node{
	int l = 0,r = 0;
	int val = 0;
}nodes[N * K];
int cnt = 1;
int upd(int v,int tl,int tr,int pos,int val){
	int nwnode = ++cnt;
	nodes[nwnode] = nodes[v];
	if(tl == tr){
		nodes[nwnode].val += val;
		return nwnode;
	}
	int tm = (tl + tr)/2;
	if(pos <= tm){
		if(nodes[v].l == 0){
			nodes[v].l = ++cnt;
		}
		nodes[nwnode].l = upd(nodes[v].l,tl,tm,pos,val);
	}
	else{
		if(nodes[v].r == 0){
			nodes[v].r = ++cnt;
		}
		nodes[nwnode].r = upd(nodes[v].r,tm+1,tr,pos,val);
	}
	nodes[nwnode].val = nodes[nodes[nwnode].l].val + nodes[nodes[nwnode].r].val;
	return nwnode;
}
int get(int v,int tl,int tr,int l,int r){
	if(v == 0 || tr < l || r < tl)
		return 0;
	if(l <= tl && tr <= r){
		return nodes[v].val;
	}
	int tm = (tl + tr)/2;
	return get(nodes[v].l,tl,tm,l,r) + get(nodes[v].r,tm+1,tr,l,r);
}
int root[N];
int n;
vector<int> tmp[N];
void init(int n_, int a[], int b[]) {
	n = n_;
	for(int i = 0;i<n;i++){
		tmp[a[i]].push_back(b[i]);
	}
	root[0] = upd(1,1,n+1,n+1,n);
	for(int i = 1;i<=n+1;i++){
		int last = root[i-1];
		for(auto u:tmp[i]){
			last = upd(last,1,n+1,u,1);
		}
		last = upd(last,1,n+1,i-1,-get(1,1,n+1,i-1,i-1));
		root[i] = last;
	} 
}
pair<int,int> val[N];
int can(int m, int k[]) {
	map<int,int> mp;
	sort(k,k+m);	
	long long sum = 0;
	for(int i = 0;i<m;i++){
		sum += k[i];
		mp[k[i]]++;
	}
	if(sum > n)return 0;
	vector<pair<int,int>> v;
	for(auto u:mp){
		v.push_back(u);
	}
	vector<int> st;
	for(int x = 0;x<v.size();x++){
		int needed = v[x].first * v[x].second;
		int tot = 0;
		int sum = 0;
		int samesum = 0;
		int oldsum = 0;
		int rp = -1;
		int l = v[x].first-1,r = n;
		bool ok = 0;
		for(int i = st.size()-1;i>=0;i--){
			if(val[st[i]].first + 1 < v[x].first)continue;
			samesum += val[st[i]].second; 
			if(rp == -1)rp = st[i];
			if(i && val[st[i-1]].first == val[st[i]].first){
				continue;
			}
			if(get(root[v[x].first],1,n+1,v[x].first,val[st[i]].first)-   (sum + get(root[rp],1,n+1,l+1,val[st[i]].first) + oldsum) > needed){
				int ll = l, rr = val[st[i]].first-1;
				while(ll < rr){
					int mm = (ll + rr + 1)/2;
					if(get(root[v[x].first],1,n+1,v[x].first,mm)-   (sum + get(root[rp],1,n+1,l+1,mm) + oldsum) > needed){
						rr = mm-1;
					}
					else ll = mm;
				}
				l = ll;
				ok = 1;
				break;
			}
			sum += oldsum;
			sum += get(root[rp],1,n+1,l+1,val[st[i]].first);
			l = val[st[i]].first;
			oldsum = samesum;
			samesum = 0;
			rp = -1;
		}
		if(!ok){
			int ll = l, rr = n;
			while(ll < rr){
				int mm = (ll + rr + 1)/2;
				if(get(root[v[x].first],1,n+1,v[x].first,mm)-   sum - oldsum> needed){
					rr = mm-1;
				}
				else ll = mm;
			}
			l = ll;
		}
		/*
		while(l < r){
			int m = (l + r + 1)/2;
			int now = get(root[v[x].first],1,n+1,v[x].first,m);
			for(int i = 0;i<st.size();i++){
				if(val[st[i]].first + 1 < v[x].first)break;
				if(val[st[i]].first + 1 <= m)
					now -= val[st[i]].second;
				int p1 = min(val[st[i]].first,m);
				int p2 = v[x].first;
				if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
				if(p1 >= p2)
					now -= get(root[st[i]],1,n+1,p2,p1);
			}
			if(now <= needed){
				l = m;
			}
			else r = m-1;
		}*/
		tot = get(root[v[x].first],1,n+1,v[x].first,l);
		for(int i = 0;i<st.size();i++){
			if(val[st[i]].first + 1< v[x].first)break;
			if(val[st[i]].first + 1 <= l)
				tot -= val[st[i]].second;
			int p1 = min(val[st[i]].first,l);
			int p2 = v[x].first;
			if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
			if(p1 >= p2)
				tot -= get(root[st[i]],1,n+1,p2,p1);
		}
		val[v[x].first] = {l,needed-tot};
		while(st.size() && val[st.back()].first < val[v[x].first].first){
			st.pop_back();
		}
		st.push_back(v[x].first);
		if(val[v[x].first].first == n && val[v[x].first].second)return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int can(int, int*)':
teams.cpp:76: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]
   76 |  for(int x = 0;x<v.size();x++){
      |                ~^~~~~~~~~
teams.cpp:79:7: warning: declaration of 'sum' shadows a previous local [-Wshadow]
   79 |   int sum = 0;
      |       ^~~
teams.cpp:65:12: note: shadowed declaration is here
   65 |  long long sum = 0;
      |            ^~~
teams.cpp:85:24: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   85 |   for(int i = st.size()-1;i>=0;i--){
      |               ~~~~~~~~~^~
teams.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |   for(int i = 0;i<st.size();i++){
      |                 ~^~~~~~~~~~
teams.cpp:149:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if(i+1 != st.size())p2 = max(p2,val[st[i+1]].first + 1);
      |       ~~~~^~~~~~~~~~~~
teams.cpp:83:24: warning: unused variable 'r' [-Wunused-variable]
   83 |   int l = v[x].first-1,r = n;
      |                        ^

Subtask #1
21.0 / 21.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 58868 KB Output is correct
2 Correct 100 ms 58876 KB Output is correct
3 Correct 104 ms 58900 KB Output is correct
4 Correct 114 ms 59220 KB Output is correct
5 Correct 75 ms 57756 KB Output is correct
6 Correct 68 ms 57804 KB Output is correct
7 Correct 66 ms 57800 KB Output is correct
8 Correct 57 ms 57744 KB Output is correct
9 Correct 67 ms 57924 KB Output is correct
10 Correct 68 ms 56772 KB Output is correct
11 Correct 61 ms 57900 KB Output is correct
12 Correct 69 ms 56760 KB Output is correct
13 Correct 77 ms 57148 KB Output is correct
14 Correct 78 ms 59388 KB Output is correct
15 Correct 98 ms 59836 KB Output is correct
16 Correct 102 ms 59860 KB Output is correct
17 Correct 66 ms 58784 KB Output is correct
18 Correct 78 ms 58728 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 59252 KB Output is correct
2 Correct 118 ms 59372 KB Output is correct
3 Correct 998 ms 62996 KB Output is correct
4 Correct 113 ms 59268 KB Output is correct
5 Correct 272 ms 58108 KB Output is correct
6 Correct 199 ms 58128 KB Output is correct
7 Correct 120 ms 58236 KB Output is correct
8 Correct 197 ms 58164 KB Output is correct
9 Correct 67 ms 57904 KB Output is correct
10 Correct 64 ms 57044 KB Output is correct
11 Correct 98 ms 58220 KB Output is correct
12 Correct 371 ms 57052 KB Output is correct
13 Correct 502 ms 59048 KB Output is correct
14 Correct 993 ms 63232 KB Output is correct
15 Correct 347 ms 60840 KB Output is correct
16 Correct 324 ms 60784 KB Output is correct
17 Correct 225 ms 59476 KB Output is correct
18 Correct 231 ms 59128 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 273768 KB Output is correct
2 Correct 780 ms 273968 KB Output is correct
3 Correct 2902 ms 283660 KB Output is correct
4 Correct 619 ms 274268 KB Output is correct
5 Correct 823 ms 268556 KB Output is correct
6 Correct 703 ms 268424 KB Output is correct
7 Correct 326 ms 268436 KB Output is correct
8 Correct 645 ms 268556 KB Output is correct
9 Correct 312 ms 267200 KB Output is correct
10 Correct 306 ms 267236 KB Output is correct
11 Correct 544 ms 267300 KB Output is correct
12 Correct 1112 ms 267588 KB Output is correct
13 Correct 1681 ms 275392 KB Output is correct
14 Correct 3196 ms 287276 KB Output is correct
15 Correct 1063 ms 279692 KB Output is correct
16 Correct 1103 ms 279592 KB Output is correct
17 Correct 727 ms 273976 KB Output is correct
18 Correct 744 ms 274116 KB Output is correct