제출 #67859

#제출 시각아이디문제언어결과실행 시간메모리
67859funcsr팀들 (IOI15_teams)C++17
0 / 100
3298 ms525312 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...