이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int MAX = 505050;
const int INF = INT_MAX >> 1;
const ll LINF = LLONG_MAX >> 1;
const ll mod = 1e9+9;
struct Node {
int l, r, val;
Node(int l, int r, int val) : l(l), r(r), val(val) {}
};
int n, root[MAX];
vector <Node> tree;
pii arr[MAX];
void expand_tree(int s, int e, int k, int pnd, int cnd) {
tree[cnd].val = tree[pnd].val + 1;
if(s == e) return;
int m = s + e >> 1;
if(k <= m) {
tree[cnd].r = tree[pnd].r;
tree[cnd].l = tree.size();
tree.eb(0, 0, 0);
expand_tree(s, m, k, tree[pnd].l, tree[cnd].l);
}
else {
tree[cnd].l = tree[pnd].l;
tree[cnd].r = tree.size();
tree.eb(0, 0, 0);
expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r);
}
}
int cal(int s, int e, int l, int r, int pnd, int cnd) {
if(s > r || e < l) return 0;
if(s >= l && e <= r) return tree[cnd].val - tree[pnd].val;
int m = s + e >> 1;
return cal(s, m, l, r, tree[pnd].l, tree[cnd].l)
+ cal(m+1, e, l, r, tree[pnd].r, tree[cnd].r);
}
void init(int N, int A[], int B[]) {
n = N;
for(int i = 0; i < n; i++) {
arr[i] = make_pair(B[i], A[i]);
}
sort(arr, arr+n);
tree.eb(0, 0, 0);
for(int i = 0; i < n; i++) {
root[i+1] = tree.size();
tree.eb(0, 0, 0);
expand_tree(1, n, arr[i].se, root[i], root[i+1]);
}
return;
}
int can(int M, int K[]) {
ll temp = 0;
for(int i = 0; i < M; i++) temp += K[i];
if(temp > n) return 0;
sort(K, K+M, [](int a, int b){return a > b;});
int pre = n + 1, cnt = 0, sum = 0;
for(int i = 0; i < M; i++) {
sum += K[i];
int nxt = lower_bound(arr, arr+n, make_pair(K[i], 0))-arr+1;
int temp = cal(1, n, 1, K[i], root[nxt-1], root[n]);
cnt += cal(1, n, 1, K[i], root[nxt-1], root[pre-1]);
if(cnt < sum) return 0;
if(temp < K[i]) return 0;
pre = nxt;
}
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:21:30: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
Node(int l, int r, int val) : l(l), r(r), val(val) {}
^
teams.cpp:20:12: note: shadowed declaration is here
int l, r, val;
^~~
teams.cpp:21:30: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
Node(int l, int r, int val) : l(l), r(r), val(val) {}
^
teams.cpp:20:9: note: shadowed declaration is here
int l, r, val;
^
teams.cpp:21:30: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
Node(int l, int r, int val) : l(l), r(r), val(val) {}
^
teams.cpp:20:6: note: shadowed declaration is here
int l, r, val;
^
teams.cpp: In function 'void expand_tree(int, int, int, int, int)':
teams.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
teams.cpp:34:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
tree[cnd].l = tree.size();
~~~~~~~~~^~
teams.cpp:40:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
tree[cnd].r = tree.size();
~~~~~~~~~^~
teams.cpp: In function 'int cal(int, int, int, int, int, int)':
teams.cpp:49:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s + e >> 1;
~~^~~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:62:24: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
root[i+1] = tree.size();
~~~~~~~~~^~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:77:60: warning: conversion to 'int' from 'long int' may alter its value [-Wconversion]
int nxt = lower_bound(arr, arr+n, make_pair(K[i], 0))-arr+1;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~
teams.cpp:78:7: warning: declaration of 'temp' shadows a previous local [-Wshadow]
int temp = cal(1, n, 1, K[i], root[nxt-1], root[n]);
^~~~
teams.cpp:70:5: note: shadowed declaration is here
ll temp = 0;
^~~~
# | 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... |