oj.uz

Submission #106413

# Submission time Handle Problem Language Result Execution time Memory
106413 2019-04-18T11:08:16 Z figter001 Teams (IOI15_teams) C++17
0 / 100
 2310 ms 192888 KB 
#include "teams.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int nax = 5e5+50;
 
struct node{
	int val,l,r;
	node(){
		l = r = -1;
		val = 0;
	}
};
 
vector<node> seg,tmp;
 
int idx[nax],n,cnt,k,l,r;
vector<pair<int,int>> p;
 
void build(int n,int s , int e){
	if(s == e){
		seg[n].val = 0;
		return;
	}
	seg[n].l = cnt++;
	seg[n].r = cnt++;
	build(seg[n].l,s,(s+e)/2);
	build(seg[n].r,(s+e)/2+1,e);
}
 
int update(int n , int s , int e,int at){
	if(s > at || e < at)
		return n;
	int newId = cnt++;
	seg[newId].val = seg[n].val;
	if(s == e){
		seg[newId].val++;
		return newId;
	}
	seg[newId].l = update(seg[n].l,s,(s+e)/2,at);
	seg[newId].r = update(seg[n].r,(s+e)/2+1,e,at);
	seg[newId].val = seg[seg[newId].l].val + seg[seg[newId].r].val;
	return newId;
}
 
void get(int n,int s,int e){
	assert(n != -1);
	if(l > r || s > r || e < l)
		return;
	if(s == e){
		k -= min(k,seg[n].val);
		return;
	}
	if(s >= l && e <= r){
		int le = seg[n].l;
		int ri = seg[n].r; 
		if(seg[le].val <= k){
			k -= seg[le].val;
			get(ri,(s+e)/2+1,e);
		}else{
			get(le,s,(s+e)/2);
		}
	}else{
		get(seg[n].l,s,(s+e)/2);
		get(seg[n].r,(s+e)/2+1,e);
	}
}
 
void init(int N, int A[], int B[]) {
	n = N;
	seg.resize(30*n);
	for(int i=0;i<n;i++){
		p.push_back({A[i],B[i]});
		assert(B[i] <= N);
	}
	cnt = 1;
	int lst = cnt;
	build(cnt++,1,n);
	sort(p.begin(),p.end());
	for(int i=0;i<n;i++){
		int a = p[i].first;
		int b = p[i].second;
		idx[a] = cnt;
		update(lst,1,n,b);
		lst = idx[a];
	}
}
 
int can(int M, int K[]) {
	sort(K,K+M);
	pair<int,int> lst = {-1,0};
	for(int i=0;i<M;i++){
		int st = upper_bound(p.begin(),p.end(),make_pair(K[i],(int)1e9)) - p.begin();
		if(st == 0)
			return 0;
		int add = 0;
		// cout << i << endl;
		if(lst.first != -1){
			k = lst.second;
			l = K[i-1];
			r = K[i] - 1;
			get(lst.first,1,n);
			add = k;
		}
		st--;
		st = p[st].first;
		st = idx[st];
		k = K[i] + add;
		l = K[i];
		r = n;
		lst = {st,k};
		// cout << l << ' ' << r << ' ' << k << endl;
		// cout << k << ' ';
		// cout << l << ' ' << r << ' ' << k << endl;
		get(st,1,n);
		// cout << k << endl;
		assert(k >= 0);
		if(k != 0)
			return 0;
	}
	return 1;
}

Compilation message

teams.cpp: In function 'void build(int, int, int)':
teams.cpp:24:31: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void build(int n,int s , int e){
                               ^
teams.cpp:21:14: note: shadowed declaration is here
 int idx[nax],n,cnt,k,l,r;
              ^
teams.cpp: In function 'int update(int, int, int, int)':
teams.cpp:35:40: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 int update(int n , int s , int e,int at){
                                        ^
teams.cpp:21:14: note: shadowed declaration is here
 int idx[nax],n,cnt,k,l,r;
              ^
teams.cpp: In function 'void get(int, int, int)':
teams.cpp:50:27: warning: declaration of 'n' shadows a global declaration [-Wshadow]
 void get(int n,int s,int e){
                           ^
teams.cpp:21:14: note: shadowed declaration is here
 int idx[nax],n,cnt,k,l,r;
              ^
teams.cpp: In function 'int can(int, int*)':
teams.cpp:97:68: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type {aka long int}' may alter its value [-Wconversion]
   int st = upper_bound(p.begin(),p.end(),make_pair(K[i],(int)1e9)) - p.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Incorrect 3 ms 384 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 37632 KB Output is correct
2 Correct 154 ms 37612 KB Output is correct
3 Correct 131 ms 37764 KB Output is correct
4 Correct 126 ms 37868 KB Output is correct
5 Correct 68 ms 37488 KB Output is correct
6 Correct 58 ms 37488 KB Output is correct
7 Incorrect 72 ms 37488 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 37996 KB Output is correct
2 Correct 125 ms 37996 KB Output is correct
3 Correct 580 ms 40900 KB Output is correct
4 Correct 122 ms 38036 KB Output is correct
5 Correct 173 ms 37568 KB Output is correct
6 Correct 195 ms 37580 KB Output is correct
7 Incorrect 163 ms 37612 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 923 ms 187132 KB Output is correct
2 Correct 853 ms 187288 KB Output is correct
3 Correct 2310 ms 192888 KB Output is correct
4 Correct 896 ms 187104 KB Output is correct
5 Correct 704 ms 185028 KB Output is correct
6 Correct 622 ms 185308 KB Output is correct
7 Incorrect 731 ms 185264 KB Output isn't correct
8 Halted 0 ms 0 KB -