제출 #624527

#제출 시각아이디문제언어결과실행 시간메모리
624527StavabFountain (eJOI20_fountain)C++14
100 / 100
396 ms28220 KiB
#include <iostream> #include <vector> #include <cmath> using namespace std; int depth; vector<pair<int, int>> nums; vector<int> segTree; vector<vector<int>> parent, sumEdges; void build(int v, int l, int r) { if(l == r) { segTree[v] = nums[l].first; } else { int m = (l + r) / 2; build(2*v, l, m); build(2*v + 1, m + 1, r); segTree[v] = max(segTree[2*v], segTree[2*v + 1]); } } void erase(int target, int v, int l, int r) { if(l == r) { segTree[v] = 0; } else { int m = (l + r) / 2; if(target <= m) erase(target, 2*v, l, m); else erase(target, 2*v + 1, m + 1, r); segTree[v] = max(segTree[2*v], segTree[2*v + 1]); } } int findParent(int val, int v, int l, int r) { if(l == r) { return l; } else { int m = (l + r) / 2; if(segTree[2*v] > val) return findParent(val, 2*v, l, m); else if(segTree[2*v + 1] > val) return findParent(val, 2*v + 1, m + 1, r); else return 0; } } void binaryUplifting() { for(int i = 1; i < depth; i++) { for(int j = 0; j < parent.size(); j++) { if(parent[j][i - 1] == -1) { parent[j][i] = -1; continue; } parent[j][i] = parent[parent[j][i - 1]][i - 1]; if(parent[j][i] != -1) sumEdges[j][i] = sumEdges[j][i - 1] + sumEdges[parent[j][i - 1]][i - 1]; } } } int main() { int n, m; scanf("%d %d", &n, &m); nums.assign(n + 1, pair<int, int>()); segTree.assign(4*n, 0); int d, c; for(int i = 1; i <= n; i++) { scanf("%d %d", &d, &c); nums[i] = make_pair(d, c); } build(1, 1, n); depth = log2(n) + 2; parent.assign(n + 1, vector<int>(depth)); sumEdges.assign(n + 1, vector<int>(depth)); parent[0][0] = -1; sumEdges[0][0] = -1; for(int i = 1; i <= n; i++) { erase(i, 1, 1, n); parent[i][0] = findParent(nums[i].first, 1, 1, n); sumEdges[i][0] = nums[i].second; } binaryUplifting(); int r, v; while(m--) { scanf("%d %d", &r, &v); int curNode = r, curReach = depth - 1; while(curReach >= 0) { if(parent[curNode][curReach] == -1) { curReach--; continue; } if(sumEdges[curNode][curReach] < v) { v -= sumEdges[curNode][curReach]; curNode = parent[curNode][curReach]; } curReach--; } printf("%d\n", curNode); } return 0; }

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

fountain.cpp: In function 'void binaryUplifting()':
fountain.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j < parent.size(); j++)
      |                        ~~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:90:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf("%d %d", &d, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:124:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         scanf("%d %d", &r, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...