이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
pair<int, int> arrpii[maxn];
int n, order[maxn], last[maxn], where[maxn];
struct node
{
int val, ct;
node *l, *r;
node()
{
val = INT_MAX, ct = 0;
l = NULL, r = NULL;
}
} *allseg[maxn];
void build(node *sth, int curl, int curr)
{
if (curl == curr)
return;
sth->l = new node, sth->r = new node;
build(sth->l, curl, (curl + curr) / 2);
build(sth->r, (curl + curr) / 2 + 1, curr);
}
node *update(node *old, int curl, int curr, int in, int val)
{
node *tmp = new node;
if (curl == curr)
{
tmp->val = val;
tmp->ct = 1;
return tmp;
}
int mid = (curl + curr) / 2;
if (in <= mid)
{
tmp->l = update(old->l, curl, mid, in, val);
tmp->r = old->r;
}
else
{
tmp->l = old->l;
tmp->r = update(old->r, mid + 1, curr, in, val);
}
tmp->ct = tmp->l->ct + tmp->r->ct;
tmp->val = min(tmp->l->val, tmp->r->val);
return tmp;
}
void init(int N, int A[], int B[])
{
n = N;
for (int i = 0; i < N; i++)
arrpii[i] = {A[i], B[i]};
sort(arrpii, arrpii + N, [](pair<int, int> a, pair<int, int> b)
{ return a.second < b.second; });
for (int i = 0; i < n; i++)
order[i] = i;
sort(order, order + n, [](int a, int b)
{ return arrpii[a] > arrpii[b]; });
for (int i = 0; i < n; i++)
where[order[i]] = i;
allseg[0] = new node;
build(allseg[0], 0, n - 1);
for (int i = 0; i < n; i++)
allseg[i + 1] = update(allseg[i], 0, n - 1, where[i], arrpii[i].first);
}
int query(node *curl, node *curr, int val)
{
if (curr->ct - curl->ct < val)
return -1;
if (curl->l == NULL)
return curr->val;
if (curr->l->ct - curl->l->ct >= val)
return query(curl->l, curr->l, val);
return query(curl->r, curr->r, val - (curr->l->ct - curl->l->ct));
}
int howmany(node *cur, int curl, int curr, int ranger, int rangel)
{
if (rangel > arrpii[order[curl]].first || arrpii[order[curr]].first > ranger)
return 0;
if (ranger >= arrpii[order[curl]].first && arrpii[order[curr]].first >= rangel)
return cur->ct;
return howmany(cur->l, curl, (curl + curr) / 2, ranger, rangel) + howmany(cur->r, (curl + curr) / 2 + 1, curr, ranger, rangel);
}
int can(int M, int K[])
{
sort(K, K + M, greater<int>());
int extra = 0, furthest = INT_MAX;
for (int i = 0; i < M; i++)
{
int pos = lower_bound(arrpii, arrpii + n, make_pair(INT_MIN, K[i]), [](pair<int, int> a, pair<int, int> b)
{ return a.second < b.second; }) -
arrpii;
if (pos == n)
return 0;
if (K[i] < furthest)
{
furthest = K[i];
extra = 0;
}
node *bef = allseg[pos], *all = allseg[n];
int ctbef = howmany(all, 0, n - 1, INT_MAX, furthest + 1) - howmany(bef, 0, n - 1, INT_MAX, furthest + 1);
int needto = K[i] + extra + ctbef;
int k = query(bef, all, needto);
if (k == -1)
return 0;
extra = needto - (howmany(all, 0, n - 1, INT_MAX, k + 1) - howmany(bef, 0, n - 1, INT_MAX, k + 1));
}
return 1;
}
// int main()
// {
// // freopen("teams.in", "r", stdin);
// // freopen("teams.out", "w", stdout);
// int N;
// cin >> N;
// int *A = (int *)malloc(sizeof(int) * (unsigned int)N);
// int *B = (int *)malloc(sizeof(int) * (unsigned int)N);
// for (int i = 0; i < N; ++i)
// {
// cin >> A[i] >> B[i];
// }
// init(N, A, B);
// int Q;
// cin >> Q;
// for (int i = 0; i < Q; ++i)
// {
// int M;
// cin >> M;
// int *K = (int *)malloc(sizeof(int) * (unsigned int)M);
// for (int j = 0; j < M; ++j)
// {
// cin >> K[j];
// }
// cout << can(M, K) << '\n';
// }
// return 0;
// }
컴파일 시 표준 에러 (stderr) 메시지
teams.cpp: In function 'int can(int, int*)':
teams.cpp:102:60: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
101 | int pos = lower_bound(arrpii, arrpii + n, make_pair(INT_MIN, K[i]), [](pair<int, int> a, pair<int, int> b)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
102 | { return a.second < b.second; }) -
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^
103 | arrpii;
| ~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |