oj.uz

Submission #150742

# Submission time Handle Problem Language Result Execution time Memory
150742 2019-09-01T08:53:02 Z 이 대회 미분 되나요?(#3668, wookje, edenooo, jms100300) King of Chairs (FXCUP4_chairs) C++17
95 / 100
 312 ms 41396 KB 
#include "king.h"
#include<queue>
#include<algorithm>
using namespace std;

#define ll long long

int N;
ll ret = 0;
priority_queue<int> pq;
struct abc {
	int idx, val;
	bool operator <(abc a)const {
		return val < a.val;
	}
};

long long SendInfo(std::vector<int> W, std::vector<int> C) {
	vector<abc> v;
	N = W.size();
	for (int i = 0; i < N; i++)
		pq.push(-C[i]);
	sort(W.begin(), W.end());
	for (int i = 0; i < N; i++)
	{
		while (!pq.empty() && W[i] > -pq.top()) pq.pop();
		if (pq.empty()) break;
		ret = W[i];
		pq.pop();
	}
	for (int i = 0; i < N; i++) {
		v.push_back({ i,C[i] });
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < N; i++) {
		if (v[i].val > ret) {
			ret = v[i].idx;
			break;
		}
		if (i == N-1) {
			ret = N-1;
		}
	}
	return ret;
}

#include "vassal.h"
#include<vector>
#include <cstdio>
#include<algorithm>
using namespace std;

#define SZ 1'000'000

long long BB;
int NN;
int seg[2100000];
vector<int> x[1000101];
struct abc {
	int idx, val;
	bool operator <(abc a)const {
		return val < a.val;
	}
};

int Update(int idx, int val, int n, int l, int r)
{
	if (r < idx || idx < l) return seg[n];
	if (l == r) return seg[n] += val;
	int mid = l + r >> 1;
	return seg[n] = Update(idx, val, n * 2, l, mid) + Update(idx, val, n * 2 + 1, mid + 1, r);
}

int Query(int L, int R, int n, int l, int r)
{
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return seg[n];
	int mid = l + r >> 1;
	return Query(L, R, n * 2, l, mid) + Query(L, R, n * 2 + 1, mid + 1, r);
}

int Kth(int k, int n, int l, int r)
{
	if (l == r) return l;
	int mid = l + r >> 1;
	if (k <= seg[n * 2]) return Kth(k, n * 2, l, mid);
	return Kth(k - seg[n * 2], n * 2 + 1, mid + 1, r);
}

void Init(long long B, std::vector<int> C){
	NN = C.size();
	for (int i = 0; i < NN; i++)
	{
		Update(C[i], 1, 1, 1, SZ);
		x[C[i]].push_back(i);
	}
	if (B != NN) BB = C[B];
	else BB = 1e9;
}

int Maid(int W){
	if (W > BB) return -1;
	if (Query(W, SZ, 1, 1, SZ) == 0) return -1;
	int cnt = Query(0, W - 1, 1, 1, SZ) + 1;
	int idx = Kth(cnt, 1, 1, SZ);
	int ret = x[idx].back();
	Update(idx, -1, 1, 1, SZ);
	x[idx].pop_back();
	return ret;
}

Compilation message

vassal.cpp: In function 'int Update(int, int, int, int, int)':
vassal.cpp:24:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
vassal.cpp: In function 'int Query(int, int, int, int, int)':
vassal.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
vassal.cpp: In function 'int Kth(int, int, int, int)':
vassal.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24612 KB Correct
2 Correct 24 ms 24740 KB Correct
3 Correct 24 ms 24856 KB Correct
4 Correct 24 ms 24780 KB Correct
5 Correct 23 ms 24860 KB Correct

Subtask #2
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 37224 KB Correct
2 Correct 203 ms 40720 KB Correct
3 Correct 184 ms 41256 KB Correct
4 Correct 221 ms 41184 KB Correct
5 Correct 211 ms 41184 KB Correct
6 Correct 219 ms 41268 KB Correct
7 Correct 177 ms 41256 KB Correct

Subtask #3
40.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 191 ms 37356 KB B = 50983
2 Partially correct 273 ms 40752 KB B = 91396
3 Partially correct 224 ms 41360 KB B = 91327
4 Partially correct 312 ms 41396 KB B = 99839
5 Partially correct 286 ms 41260 KB B = 99579
6 Partially correct 294 ms 41268 KB B = 99741
7 Partially correct 221 ms 41276 KB B = 91342
8 Correct 151 ms 35060 KB Correct