제출 #387492

#제출 시각아이디문제언어결과실행 시간메모리
387492ParsaAlizadeh팀들 (IOI15_teams)C++17
77 / 100
1277 ms524292 KiB
#include <bits/stdc++.h> #include "teams.h" using namespace std; typedef pair<int, int> pii; struct Node : enable_shared_from_this<Node> { int cnt; shared_ptr<Node> lc, rc; Node() : cnt(0) {} void init() { lc = shared_from_this(); rc = shared_from_this(); } shared_ptr<Node> add(int l, int r, int ind) { if (ind < l || r <= ind) return shared_from_this(); shared_ptr<Node> cur = make_shared<Node>(); if (r - l == 1) { cur->init(); cur->cnt = cnt + 1; return cur; } int mid = (l + r) >> 1; cur->lc = lc->add(l, mid, ind); cur->rc = rc->add(mid, r, ind); cur->cnt = cnt + 1; return cur; } int get(shared_ptr<Node> const& prv, int l, int r, int qr) { if (qr <= l) return 0; if (r <= qr) return cnt - prv->cnt; int mid = (l + r) >> 1; return lc->get(prv->lc, l, mid, qr) + rc->get(prv->rc, mid, r, qr); } int query(shared_ptr<Node> const& prv, int l, int r, int t) { if (cnt - prv->cnt < t) return r; if (r - l == 1) return l; int mid = (l + r) >> 1; int lft = lc->cnt - prv->lc->cnt; if (lft >= t) return lc->query(prv->lc, l, mid, t); return rc->query(prv->rc, mid, r, t - lft); } shared_ptr<Node> sub(shared_ptr<Node> const& prv, int l, int r, int qr) { if (qr <= l) return prv; if (r <= qr) return shared_from_this(); int mid = (l + r) >> 1; shared_ptr<Node> cur = make_shared<Node>(); cur->lc = lc->sub(prv->lc, l, mid, qr); cur->rc = rc->sub(prv->rc, mid, r, qr); cur->cnt = cur->lc->cnt + cur->rc->cnt; return cur; } }; int n; vector<shared_ptr<Node>> root; vector<int> R; vector<pii> vec; void init(int n, int A[], int B[]) { ::n = n; for (int i = 0; i < n; i++) { vec.emplace_back(B[i], A[i]); } sort(begin(vec), end(vec)); vector<int> L[n]; for (int i = 0; i < n; i++) { L[vec[i].second - 1].push_back(i); } R.resize(n + 1); root.push_back(make_shared<Node>()); root[0]->init(); for (int i = 0; i < n; i++) { root.push_back(root[i]); for (int j : L[i]) { root[i + 1] = root[i + 1]->add(0, n, j); } R[i + 1] = lower_bound(begin(vec), end(vec), pii{i + 1, -1}) - begin(vec); } } int can(int M, int K[]) { sort(K, K + M); shared_ptr<Node> cur = make_shared<Node>(); cur->init(); for (int i = 0; i < M; i++) { int t = root[K[i]]->get(cur, 0, n, R[K[i]]); int qr = root[K[i]]->query(cur, 0, n, t + K[i]); if (qr == n || vec[qr].first < K[i]) return 0; cur = root[K[i]]->sub(cur, 0, n, qr + 1); } return 1; }

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

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:74:34: warning: declaration of 'n' shadows a global declaration [-Wshadow]
   74 | void init(int n, int A[], int B[]) {
      |                                  ^
teams.cpp:69:5: note: shadowed declaration is here
   69 | int n;
      |     ^
teams.cpp:92:70: warning: conversion from '__gnu_cxx::__normal_iterator<std::pair<int, int>*, std::vector<std::pair<int, int> > >::difference_type' {aka 'long int'} to '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} may change value [-Wconversion]
   92 |         R[i + 1] = lower_bound(begin(vec), end(vec), pii{i + 1, -1}) - begin(vec);
      |                    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...