제출 #172435

#제출 시각아이디문제언어결과실행 시간메모리
172435gs18103팀들 (IOI15_teams)C++14
0 / 100
1337 ms216684 KiB
#include "teams.h" #include <bits/stdc++.h> #define fi first #define se second #define eb emplace_back #define em emplace #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef pair <int, int> pii; typedef pair <ll, ll> pll; const int MAX = 505050; const int INF = INT_MAX >> 1; const ll LINF = LLONG_MAX >> 1; const ll mod = 1e9+9; struct Node { int l, r, val; Node(int l, int r, int val) : l(l), r(r), val(val) {} }; int n, root[MAX], h[MAX]; vector <Node> tree; vector <int> num, numx; pii arr[MAX]; void expand_tree(int s, int e, int k, int pnd, int cnd) { tree[cnd].val = tree[pnd].val + 1; if(s == e) return; int m = s + e >> 1; if(k <= m) { tree[cnd].r = tree[pnd].r; tree[cnd].l = tree.size(); tree.eb(0, 0, 0); expand_tree(s, m, k, tree[pnd].l, tree[cnd].l); } else { tree[cnd].l = tree[pnd].l; tree[cnd].r = tree.size(); tree.eb(0, 0, 0); expand_tree(m+1, e, k, tree[pnd].r, tree[cnd].r); } } void init(int N, int A[], int B[]) { n = N; for(int i = 0; i < n; i++) { arr[i] = make_pair(A[i], B[i]); num.eb(B[i]); numx.eb(A[i]); } sort(all(num)); sort(all(numx)); sort(arr, arr+n, [](pii a, pii b) { if(a.se == b.se) return a.fi < b.fi; return a.se < b.se; }); for(int i = 0; i < n; i++) { arr[i].se = i + 1; } sort(arr, arr+n); tree.eb(0, 0, 0); for(int i = 0; i < n; i++) { root[i+1] = tree.size(); tree.eb(0, 0, 0); expand_tree(1, n, arr[i].se, root[i], root[i+1]); } return; } int cal(int s, int e, int l, int r, int pnd, int cnd) { if(s > r || e < l || l > r) return 0; if(s >= l && e <= r) return tree[cnd].val - tree[pnd].val; int m = s + e >> 1; return cal(s, m, l, r, tree[pnd].l, tree[cnd].l) + cal(m+1, e, l, r, tree[pnd].r, tree[cnd].r); } int get_r(int s, int e, int cnt, int pnd, int cnd) { if(s == e) return s; int m = s + e >> 1, lcnt = tree[tree[cnd].l].val - tree[tree[pnd].l].val; if(lcnt <= cnt) return get_r(s, m, cnt, tree[pnd].l, tree[cnd].l); else return get_r(m+1, e, cnt - lcnt, tree[pnd].r, tree[cnd].r); } int can(int M, int K[]) { ll temp = 0; for(int i = 0; i < M; i++) temp += K[i]; if(temp > n) return 0; sort(K, K+M); stack <pii> stk; stk.em(0, n+1); for(int i = 0; i < M; i++) { int last = lower_bound(all(num), K[i]) - num.begin() + 1, cnt = K[i]; int rx = upper_bound(all(numx), K[i]) - numx.begin(); while(!stk.empty() && stk.top().se < last) stk.pop(); while(!stk.empty()) { int x = stk.top().fi, y = stk.top().se; int temp = cal(1, n, last, y, root[x], root[rx]); if(temp < cnt) { cnt -= temp; last = y + 1; stk.pop(); } else { int l = cal(1, n, 1, last, root[x], root[rx]); int ny = get_r(1, n, l + cnt, root[x], root[rx]); stk.em(rx, ny); break; } } if(stk.empty()) return 0; } return 1; }

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

teams.cpp: In constructor 'Node::Node(int, int, int)':
teams.cpp:21:30: warning: declaration of 'val' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:12: note: shadowed declaration is here
  int l, r, val;
            ^~~
teams.cpp:21:30: warning: declaration of 'r' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:9: note: shadowed declaration is here
  int l, r, val;
         ^
teams.cpp:21:30: warning: declaration of 'l' shadows a member of 'Node' [-Wshadow]
  Node(int l, int r, int val) : l(l), r(r), val(val) {}
                              ^
teams.cpp:20:6: note: shadowed declaration is here
  int l, r, val;
      ^
teams.cpp: In function 'void expand_tree(int, int, int, int, int)':
teams.cpp:32:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp:35:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].l = tree.size();
                 ~~~~~~~~~^~
teams.cpp:41:26: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   tree[cnd].r = tree.size();
                 ~~~~~~~~~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:66:24: warning: conversion to 'int' from 'std::vector<Node>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   root[i+1] = tree.size();
               ~~~~~~~~~^~
teams.cpp: In function 'int cal(int, int, int, int, int, int)':
teams.cpp:76:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1;
          ~~^~~
teams.cpp: In function 'int get_r(int, int, int, int, int)':
teams.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s + e >> 1, lcnt = tree[tree[cnd].l].val - tree[tree[pnd].l].val;
          ~~^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:97:56: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int last = lower_bound(all(num), K[i]) - num.begin() + 1, cnt = K[i];
              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
teams.cpp:98:41: warning: conversion to 'int' from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type {aka long int}' may alter its value [-Wconversion]
   int rx = upper_bound(all(numx), K[i]) - numx.begin();
            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
teams.cpp:102:8: warning: declaration of 'temp' shadows a previous local [-Wshadow]
    int temp = cal(1, n, last, y, root[x], root[rx]);
        ^~~~
teams.cpp:89:5: note: shadowed declaration is here
  ll temp = 0;
     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...