oj.uz

답안 #774980

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
774980 2023-07-06T06:26:07 Z ngrace 팀들 (IOI15_teams) C++14
100 / 100
 3942 ms 215232 KB 
#include "teams.h"
 
#include <bits/stdc++.h>
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second
 
struct node{
    int l;
    int r;
    int sum;
};
int nodecnt=0;
v<node> nodes;
int newNode(int l, int r){
	int ndc = nodecnt++;
	nodes.push_back(node());
	nodes[ndc].l=l;
	nodes[ndc].r=r;
	nodes[ndc].sum = nodes[nodes[ndc].l].sum + nodes[nodes[ndc].r].sum;
	return ndc;
}
int build(int l, int r){
    if(l==r){
		nodes.push_back(node());
		nodes[nodecnt].l = -1;
		nodes[nodecnt].r = -1;
		nodes[nodecnt].sum=0;
		return nodecnt++;
	}
    int m=(l+r)/2;
	return newNode(build(l, m), build(m+1, r));
}
int update(int cur, int l, int r, int tar){
    if(l==r) {
		nodes.push_back(node());
		nodes[nodecnt].l = -1;
		nodes[nodecnt].r = -1;
		nodes[nodecnt].sum=nodes[cur].sum+1;
		return nodecnt++;
	}
    int m=(l+r)/2;
    if(tar<=m){
		return newNode(update(nodes[cur].l, l, m, tar), nodes[cur].r);
	}
	return newNode(nodes[cur].l, update(nodes[cur].r, m+1, r, tar));
}
int query(int cur, int l, int r, int ql){
    if(ql<=l) return nodes[cur].sum;
    int m=(l+r)/2, ret=0;
    if(ql<=m) ret += query(nodes[cur].l, l, m, ql);
    ret += query(nodes[cur].r, m+1, r, ql);
	return ret;
}
int binSearchQuery(int curl, int curr, int l, int r, int num){ 
	//returns last place where num<amount holds
	if(l==r) return l;
	int m=(l+r)/2;
	int amount = nodes[nodes[curr].r].sum - nodes[nodes[curl].r].sum;
	if(num >= amount) return binSearchQuery(nodes[curl].l, nodes[curr].l, l,m, num - amount);
	return binSearchQuery(nodes[curl].r, nodes[curr].r, m+1, r, num);
}
 
int n;
ii points[500000];
v<int> roots;
int getRect(int x1, int x2, int y){
	ii p1 = {x1, -1}, p2 = {x2+1, -1};
	int ind1 = distance(points, lower_bound(points, points + n, p1));
	int ind2 = distance(points, lower_bound(points, points + n, p2));
	return query(roots[ind2], 1, n, y) - query(roots[ind1], 1, n, y);
}
int getSplit(int x1, int x2, int num){
	ii p1 = {x1, -1}, p2 = {x2+1, -1};
	int ind1 = distance(points, lower_bound(points, points + n, p1));
	int ind2 = distance(points, lower_bound(points, points + n, p2));
	return binSearchQuery(roots[ind1], roots[ind2], 1, n, num) + 1;//the first place where the suffix sum is >= num
}
 
void init(int N, int A[], int B[]) {
	n=N;
	for(int i=0; i<n; i++) {
		points[i].fi=A[i];
		points[i].se=B[i];
	}
 
	roots.push_back(build(1,n));
	sort(points, points+n);
	for(ii it:points) roots.push_back(update(roots.back(), 1, n, it.se));
}
 
int cnt=0;
int can(int M, int K[]) {
	sort(K, K+M);
 
	if(M>400){
		priority_queue<ii> pq;
		int j=0;
		for(int i=0; i<M; i++){
			while(j<n && points[j].fi<=K[i]){
				pq.push({-points[j].se, points[j].fi});
				j++;
			}
			while(pq.size()>0 && -pq.top().fi<K[i]) pq.pop();
			if(pq.size()<K[i]) return 0;
			for(int k=0; k<K[i]; k++) pq.pop();
		}
		return 1;
	}
 
	v<int> dp(M);
	set<int> opt;
	v<v<ii>> pq(M+1);
	dp[0] = getRect(0, K[0], K[0]) - K[0];
	opt.insert(0);
	if(dp[0]<0) return 0;
	for(int i=1; i<M; i++){
		dp[i] = getRect(0, K[i], K[i]) - K[i];
 
		for(ii it:pq[i]){
			int j1=it.fi;
			int j2=it.se;
			if(opt.find(j1)==opt.end() || opt.find(j2)==opt.end()) continue;
			opt.erase(j2);
		}
 
		auto it=opt.end();
		it--;
		int j=*it;
		for(j=max(0,*it-2); j<min(i,*it+3); j++)
			dp[i] = min(dp[i], dp[j] + (K[i]==K[j] ? 0 : getRect(K[j]+1, K[i], K[i])) - K[i]);
 
		if(dp[i]<0) return 0;
 
		it = opt.end();
		it--;
		int j1=*it;
		int j2=i;
		int k = (K[j1]==K[j2]) ? 0 : getSplit(K[j1]+1, K[j2], dp[j2]-dp[j1]);
		if(K[j1]==K[j2]) k= (dp[j2] - dp[j1] < 0) ? K[M-1]+1 : K[j2]+1;
		auto it2 = lower_bound(K, K+M, k);
		int l = distance(K, it2);
		pq[l].push_back({j1,j2});
		if(l>i) opt.insert(i);
	}
	return 1;
}

Compilation message

teams.cpp: In function 'int getRect(int, int, int)':
teams.cpp:71:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   71 |  int ind1 = distance(points, lower_bound(points, points + n, p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:72:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   72 |  int ind2 = distance(points, lower_bound(points, points + n, p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int getSplit(int, int, int)':
teams.cpp:77:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   77 |  int ind1 = distance(points, lower_bound(points, points + n, p1));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp:78:21: warning: conversion from 'std::iterator_traits<std::pair<int, int>*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   78 |  int ind2 = distance(points, lower_bound(points, points + n, p2));
      |             ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:107:16: warning: comparison of integer expressions of different signedness: 'std::priority_queue<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  107 |    if(pq.size()<K[i]) return 0;
      |       ~~~~~~~~~^~~~~
teams.cpp:144:19: warning: conversion from 'std::iterator_traits<int*>::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  144 |   int l = distance(K, it2);
      |           ~~~~~~~~^~~~~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 28384 KB Output is correct
2 Correct 35 ms 27900 KB Output is correct
3 Correct 65 ms 51540 KB Output is correct
4 Correct 65 ms 51576 KB Output is correct
5 Correct 65 ms 51636 KB Output is correct
6 Correct 63 ms 51628 KB Output is correct
7 Correct 66 ms 51584 KB Output is correct
8 Correct 67 ms 51556 KB Output is correct
9 Correct 65 ms 51552 KB Output is correct
10 Correct 73 ms 51568 KB Output is correct
11 Correct 65 ms 51596 KB Output is correct
12 Correct 67 ms 51536 KB Output is correct
13 Correct 65 ms 51540 KB Output is correct
14 Correct 66 ms 51552 KB Output is correct
15 Correct 66 ms 51604 KB Output is correct
16 Correct 66 ms 51624 KB Output is correct
17 Correct 55 ms 52924 KB Output is correct
18 Correct 53 ms 52960 KB Output is correct
19 Correct 59 ms 53020 KB Output is correct
20 Correct 57 ms 52916 KB Output is correct
21 Correct 55 ms 52940 KB Output is correct
22 Correct 53 ms 52968 KB Output is correct
23 Correct 55 ms 52996 KB Output is correct
24 Correct 52 ms 52876 KB Output is correct
25 Correct 52 ms 52968 KB Output is correct
26 Correct 64 ms 52888 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 203876 KB Output is correct
2 Correct 207 ms 203792 KB Output is correct
3 Correct 207 ms 203804 KB Output is correct
4 Correct 219 ms 204000 KB Output is correct
5 Correct 198 ms 203468 KB Output is correct
6 Correct 190 ms 203436 KB Output is correct
7 Correct 192 ms 203500 KB Output is correct
8 Correct 194 ms 203460 KB Output is correct
9 Correct 193 ms 203532 KB Output is correct
10 Correct 191 ms 203248 KB Output is correct
11 Correct 185 ms 203244 KB Output is correct
12 Correct 189 ms 203420 KB Output is correct
13 Correct 191 ms 203596 KB Output is correct
14 Correct 200 ms 203716 KB Output is correct
15 Correct 232 ms 203836 KB Output is correct
16 Correct 208 ms 203792 KB Output is correct
17 Correct 195 ms 203928 KB Output is correct
18 Correct 196 ms 203740 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 204016 KB Output is correct
2 Correct 222 ms 204080 KB Output is correct
3 Correct 308 ms 204068 KB Output is correct
4 Correct 223 ms 204044 KB Output is correct
5 Correct 636 ms 203760 KB Output is correct
6 Correct 480 ms 203628 KB Output is correct
7 Correct 191 ms 203700 KB Output is correct
8 Correct 426 ms 203744 KB Output is correct
9 Correct 186 ms 203500 KB Output is correct
10 Correct 204 ms 203340 KB Output is correct
11 Correct 373 ms 203372 KB Output is correct
12 Correct 304 ms 203512 KB Output is correct
13 Correct 352 ms 203812 KB Output is correct
14 Correct 354 ms 203912 KB Output is correct
15 Correct 270 ms 203920 KB Output is correct
16 Correct 277 ms 204004 KB Output is correct
17 Correct 262 ms 203872 KB Output is correct
18 Correct 253 ms 203916 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 488 ms 212312 KB Output is correct
2 Correct 516 ms 212196 KB Output is correct
3 Correct 896 ms 212268 KB Output is correct
4 Correct 505 ms 212248 KB Output is correct
5 Correct 2369 ms 211820 KB Output is correct
6 Correct 3942 ms 211648 KB Output is correct
7 Correct 261 ms 211440 KB Output is correct
8 Correct 2889 ms 211436 KB Output is correct
9 Correct 252 ms 211948 KB Output is correct
10 Correct 448 ms 211284 KB Output is correct
11 Correct 2501 ms 211348 KB Output is correct
12 Correct 518 ms 211332 KB Output is correct
13 Correct 720 ms 212812 KB Output is correct
14 Correct 1018 ms 213712 KB Output is correct
15 Correct 626 ms 213740 KB Output is correct
16 Correct 545 ms 215232 KB Output is correct
17 Correct 398 ms 214652 KB Output is correct
18 Correct 395 ms 214580 KB Output is correct