제출 #828508

#제출 시각아이디문제언어결과실행 시간메모리
828508Josia팀들 (IOI15_teams)C++17
100 / 100
3809 ms229324 KiB
#include "teams.h" #include <bits/stdc++.h> using namespace std; // #define int int64_t int n; struct Query { struct seg { struct node { int val = 0; int l = -1; int r = -1; }; vector<node> tree = {{0, -1, -1}}; void build(int v, int rl, int rr) { if (rl == rr) return; tree[v].l = tree.size(); tree.push_back(node()); tree[v].r = tree.size(); tree.push_back(node()); int rm = (rl + rr)/2; build(tree[v].l, rl, rm); build(tree[v].r, rm+1, rr); } int update(int v, int rl, int rr, int pos, int val) { if (rl == rr) { int newV = tree.size(); tree.push_back(tree[v]); tree[newV].val = val; return newV; } int rm = (rl + rr)/2; int newV = tree.size(); tree.push_back(tree[v]); if (pos <= rm) tree[newV].l = (update(tree[newV].l, rl, rm, pos, val)); else tree[newV].r = (update(tree[newV].r, rm+1, rr, pos, val)); tree[newV].val = tree[tree[newV].l].val + tree[tree[newV].r].val; return newV; } int query(int v, int rl, int rr, int ql, int qr) { if (ql > qr) return 0; if (rl == ql && rr == qr) return tree[v].val; int rm = (rl + rr)/2; return query(tree[v].l, rl, rm, ql, min(rm, qr)) + query(tree[v].r, rm+1, rr, max(rm+1, ql), qr); } }; vector<pair<pair<int, int>, pair<int, int>>> rangesWithSortedIndicies; vector<pair<int, int>> beginWithIndicies; vector<pair<int, int>> endWithIndicies; vector<int> startTimes; seg tree; void initQuery(vector<pair<int, int>> &ranges) { rangesWithSortedIndicies.resize(n); beginWithIndicies.resize(n); endWithIndicies.resize(n); for (int i = 0; i<n; i++) { rangesWithSortedIndicies[i].first.first = ranges[i].first; rangesWithSortedIndicies[i].second.first = ranges[i].second; } sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end()); for (int i = 0; i<n; i++) { rangesWithSortedIndicies[i].first.second = i; swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second); beginWithIndicies[i] = rangesWithSortedIndicies[i].second; } sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end()); for (int i = 0; i<n; i++) { rangesWithSortedIndicies[i].first.second = i; swap(rangesWithSortedIndicies[i].first, rangesWithSortedIndicies[i].second); endWithIndicies[i] = rangesWithSortedIndicies[i].second; } sort(rangesWithSortedIndicies.begin(), rangesWithSortedIndicies.end()); assert(is_sorted(beginWithIndicies.begin(), beginWithIndicies.end())); assert(is_sorted(endWithIndicies.begin(), endWithIndicies.end())); // ----------- rangesWithSortedIndicies: {valBegin, indBegin}, {valEnd, indEnd}; sorted by begin. ----------- tree.build(0, 0, n-1); startTimes.resize(n); for (int i = 0; i<(int)n; i++) { assert(i == rangesWithSortedIndicies[i].first.second); startTimes[i] = tree.update(i == 0 ? 0 : startTimes[i-1], 0, n-1, rangesWithSortedIndicies[i].second.second, 1); } } int query(int indexBeginL, int indexBeginR, int indexEndL, int indexEndR) { int right = tree.query(startTimes[indexBeginR], 0, n-1, indexEndL, indexEndR); int left = tree.query(indexBeginL == 0 ? 0 : startTimes[indexBeginL-1], 0, n-1, indexEndL, indexEndR); return right-left; } }; vector<int> allBeginR, allEndL; Query queryEngine; void makeAll() { allBeginR.assign(n+1, -1); allEndL.assign(n+1, -1); for (int i = 1; i<=n; i++) { auto pBeginR = lower_bound(queryEngine.beginWithIndicies.begin(), queryEngine.beginWithIndicies.end(), pair<int, int>{i, 1e9}); auto pEndL = lower_bound(queryEngine.endWithIndicies.begin(), queryEngine.endWithIndicies.end(), pair<int, int>{i-1, 1e9}); if (pBeginR != queryEngine.beginWithIndicies.begin()) allBeginR[i] = (*prev(pBeginR)).second; if (pEndL != queryEngine.endWithIndicies.end()) allEndL[i] = (*pEndL).second; } } void init(signed _N, signed A[], signed B[]) { n = _N; vector<pair<int, int>> ranges(n); for (int i = 0; i<n; i++) { ranges[i].first = A[i]; ranges[i].second = B[i]; } queryEngine.initQuery(ranges); makeAll(); } signed can(signed m, signed K[]) { map<int, int> projects; for (int i = 0; i<m; i++) { projects[K[i]]++; } vector<pair<int, int>> s; s.push_back({-1, n-1}); for (pair<int, int> i: projects) { int groupsize = i.first; int people = i.first * i.second; int cnt = 0; int beginR = allBeginR[groupsize], endL = allEndL[groupsize]; if (beginR == -1 || endL == -1) {return 0;} // esay case: this group is out of the range while (s.back().second < endL) { s.pop_back(); if (s.empty()) return 0; } while (true) { int add = queryEngine.query(s.back().first+1, beginR, endL, s.back().second); if (cnt+add >= people) break; cnt += add; endL = s.back().second+1; s.pop_back(); if (s.empty()) return 0; } int beginL = s.back().first+1; int l = endL, r = s.back().second; while (l<r) { int mid = (l+r)/2; int res = queryEngine.query(beginL, beginR, endL, mid); if (res + cnt >= people) r = mid; else l = mid+1; } s.push_back({beginR, l}); } return 1; }

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

teams.cpp: In member function 'void Query::seg::build(int, int, int)':
teams.cpp:22:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   22 |    tree[v].l = tree.size();
      |                ~~~~~~~~~^~
teams.cpp:24:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   24 |    tree[v].r = tree.size();
      |                ~~~~~~~~~^~
teams.cpp: In member function 'int Query::seg::update(int, int, int, int, int)':
teams.cpp:34:25: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   34 |     int newV = tree.size();
      |                ~~~~~~~~~^~
teams.cpp:43:24: warning: conversion from 'std::vector<Query::seg::node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |    int newV = tree.size();
      |               ~~~~~~~~~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...