제출 #287246

#제출 시각아이디문제언어결과실행 시간메모리
287246Kastanda팀들 (IOI15_teams)C++11
77 / 100
1044 ms151104 KiB
// M #include<bits/stdc++.h> #include "teams.h" using namespace std; const int N = 500005, MXS = N * 19; int n, A[N], B[N], K[N]; int ts, root[N], L[MXS], R[MXS], C[MXS]; vector < int > U, V[N]; int Add(int i, int id, int l = 1, int r = n + 1) { int ID = ++ ts; L[ID] = L[id]; R[ID] = R[id]; C[ID] = C[id] + 1; if (r - l < 2) return ID; if (i < ((l + r) >> 1)) L[ID] = Add(i, L[id], l, (l + r) >> 1); else R[ID] = Add(i, R[id], (l + r) >> 1, r); return ID; } int Count(int lid, int rid, int le, int ri, int l = 1, int r = n + 1) { if (ri <= l || r <= le) return 0; if (le <= l && r <= ri) return C[rid] - C[lid]; return Count(L[lid], L[rid], le, ri, l, (l + r) >> 1) + Count(R[lid], R[rid], le, ri, (l + r) >> 1, r); } int GetKth(int lid, int rid, int &k, int l = 1, int r = n + 1) { if (C[rid] - C[lid] < k) return n + 1; if (r - l < 2) return l; if (C[L[rid]] - C[L[lid]] >= k) return GetKth(L[lid], L[rid], k, l, (l + r) >> 1); k -= C[L[rid]] - C[L[lid]]; return GetKth(R[lid], R[rid], k, (l + r) >> 1, r); } void init(int _n, int _A[], int _B[]) { n = _n; vector < int > P(n); for (int i = 0; i < n; i ++) P[i] = i; sort(P.begin(), P.end(), [&](int i, int j){return make_pair(_B[i], _A[i]) < make_pair(_B[j], _A[j]);}); U.push_back(0); for (int i = 0; i < n; i ++) U.push_back(_B[P[i]]); for (int i = 1; i <= n; i ++) A[i] = _A[P[i - 1]], B[i] = i; for (int i = 1; i <= n; i ++) V[A[i]].push_back(i); for (int i = 1; i <= n; i ++) { root[i] = root[i - 1]; for (int j : V[i]) root[i] = Add(B[j], root[i]); } } int can(int _m, int _K[]) { int m = _m; for (int i = 1; i <= m; i ++) K[i] = _K[i - 1]; sort(K + 1, K + m + 1); vector < pair < int , int > > Stk; Stk.push_back({0, n + 1}); for (int i = 1; i <= m; i ++) { int need = K[i]; int le = lower_bound(U.begin(), U.end(), K[i]) - U.begin(); int ri = le; while (Stk.size() && need > 0) { int c = Count(root[Stk.back().first], root[K[i]], ri, Stk.back().second); if (c >= need) break; need -= c; ri = max(ri, Stk.back().second); Stk.pop_back(); } if (!Stk.size()) return 0; assert(need); int c = Count(root[Stk.back().first], root[K[i]], 1, ri); need += c; ri = GetKth(root[Stk.back().first], root[K[i]], need); if (ri > n) return 0; ri ++; assert(ri <= Stk.back().second); Stk.push_back({K[i], ri}); } return 1; }

컴파일 시 표준 에러 (stderr) 메시지

teams.cpp: In function 'int can(int, int*)':
teams.cpp:79:64: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
   79 |                 int le = lower_bound(U.begin(), U.end(), K[i]) - U.begin();
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...