이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define index(x, y) (int)(lower_bound(all(x), y)-x.begin())
#define pb push_back
#define MAX_N (1<<19)
struct Node {
int val = 0;
Node *left = NULL, *right = NULL;
inline int value(Node *x) { return x==NULL?0:x->val; }
int query(int a, int b, int k=0, int l=0, int r=MAX_N) {
if (b <= l || r <= a) return 0;
if (a <= l && r <= b) return val;
int ret = 0;
if (left) ret += left->query(a, b, k*2+1, l, (l+r)/2);
if (right) ret += right->query(a, b, k*2+2, (l+r)/2, r);
return ret;
}
Node *add(int x, int v, int k=0, int l=0, int r=MAX_N) {
if (r-l == 1) {
assert(x == l);
Node *ret = new Node();
ret->val = val+v;
return ret;
}
if (left == NULL) left = new Node();
if (right == NULL) right = new Node();
Node *ret = new Node();
if (l <= x && x < (l+r)/2) {
ret->left = left->add(x, v, k*2+1, l, (l+r)/2);
ret->right = right;
}
else {
ret->left = left;
ret->right = right->add(x, v, k*2+2, (l+r)/2, r);
}
ret->val = value(ret->left) + value(ret->right);
return ret;
}
};
int N;
vector<int> Gopen[500001];
vector<int> Gclose[500001];
Node *seg[500001];
inline int count(int l, int a, int b) { return seg[l]->query(a, b+1); }
void init(int NN, int A[], int B[]) {
N = NN;
rep(i, N) {
cout<<A[i]<<"->"<<B[i]<<"\n";
Gopen[A[i]].pb(B[i]);
Gclose[B[i]+1].pb(B[i]);
}
seg[0] = new Node();
rep(i, N+1) {
for (int r : Gopen[i]) seg[i] = seg[i]->add(r, +1);
for (int r : Gclose[i]) seg[i] = seg[i]->add(r, -1);
if (i+1 <= N) seg[i+1] = seg[i];
}
}
int can(int M, int K[]) {
long long sum = 0;
rep(i, M) sum += K[i];
if (sum > N) return 0;
sort(K, K+M);
vector<int> xs(K, K+M); uniq(xs);
//cout<<"xs={";for(int x :xs)cout<<x<<",";cout<<"}\n";
vector<int> C(xs.size(), 0);
vector<int> demand(xs.size(), 0);
rep(i, M) demand[index(xs, K[i])]+=K[i];
rep(k, xs.size()) {
for (int r=k; r<xs.size(); r++) {
int rpos = r+1==xs.size()?N:(xs[r+1]-1);
C[r] += count(xs[k], xs[r], rpos) - (k>=1?count(xs[k-1], xs[r], rpos):0);
}
//cout<<"C=";rep(i,xs.size())cout<<C[i]<<",";cout<<": demand="<<demand[k]<<"\n";
for (int r=k; r<xs.size(); r++) {
int e = min(demand[k], C[r]);
demand[k] -= e;
C[r] -= e;
}
if (demand[k] > 0) return 0;
}
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
teams.cpp: In function 'int can(int, int*)':
teams.cpp:7:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define rep(i, n) for (int i=0; i<(n); i++)
^
teams.cpp:84:3: note: in expansion of macro 'rep'
rep(k, xs.size()) {
^~~
teams.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r=k; r<xs.size(); r++) {
~^~~~~~~~~~
teams.cpp:86:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int rpos = r+1==xs.size()?N:(xs[r+1]-1);
~~~^~~~~~~~~~~
teams.cpp:90:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int r=k; r<xs.size(); r++) {
~^~~~~~~~~~
# | 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... |