제출 #787573

#제출 시각아이디문제언어결과실행 시간메모리
787573RecursiveCoGlobal Warming (CEOI18_glo)C++14
45 / 100
1291 ms262144 KiB
// CF template, version 3.0 #include <bits/stdc++.h> using namespace std; #define improvePerformance ios_base::sync_with_stdio(false); cin.tie(0) #define getTest int t; cin >> t #define eachTest for (int _var=0;_var<t;_var++) #define get(name) int (name); cin >> (name) #define out(o) cout << (o) #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); } #define sortl(name) sort((name).begin(), (name).end()) #define rev(name) reverse((name).begin(), (name).end()) #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++) #define decision(b) if (b){out("YES");}else{out("NO");} #define int long long int m; void upd(vector<int>& tree, int i, int x, int l=0, int r=m-1, int v=1) { if (l == r) tree[v] = max(tree[v], x); else { int middle = (l + r) / 2; if (middle >= i) upd(tree, i, x, l, middle, 2 * v); else upd(tree, i, x, middle + 1, r, 2 * v + 1); tree[v] = max(tree[2 * v], tree[2 * v + 1]); } } int query(vector<int>& tree, int ql, int qr, int l=0, int r=m-1, int v=1) { if (ql <= l && r <= qr) return tree[v]; if (qr < l || r < ql) return 0; int middle = (l + r) / 2; return max(query(tree, ql, qr, l, middle, 2 * v), query(tree, ql, qr, middle + 1, r, 2 * v + 1)); } signed main() { //improvePerformance; //getTest; //eachTest { get(n); get(x); getList(n, nums); vector<int> sorted; for (int num: nums) sorted.push_back(num); sortl(sorted); map<int, int> coord; m = 0; forto(n, i) { if (coord.find(sorted[i]) == coord.end()) { coord[sorted[i]] = m++; } } coord[1e18] = m; // assuming x is small enough... vector<vector<vector<int>>> dp(n, vector<vector<int>>(3, vector<int>(2 * x + 1, -1))); vector<int> segtree0(4 * m, 0); vector<int> segtree1(4 * m, 0); vector<int> segtree2(4 * m, 0); // dp[i][s][d] = LIS in the first i elements if index i is before, in or outside the interval (s=0, 1, or 2 resp.) and we increase by d. LIS must end at index i. forto(2 * x + 1, d) { forto(4 * m, i) { segtree0[i] = 0; segtree1[i] = 0; segtree2[i] = 0; } // calculate the DP values when delta = d. int D = d - x; forto(n, i) { forto(3, s) { if (s == 0) { int co = coord[nums[i]]; if (co == 0) dp[i][s][d] = 1; else { dp[i][s][d] = query(segtree0, 0, co - 1) + 1; } } else if (s == 1) { auto it = lower_bound(sorted.begin(), sorted.end(), nums[i] + D); int el = it == sorted.end()? 1e18: *it; int co = coord[el]; int cur; if (co == 0) cur = 1; else { cur = query(segtree0, 0, co - 1) + 1; } int curco = coord[nums[i]]; int second; if (curco == 0) second = 1; else { second = query(segtree1, 0, curco - 1) + 1; } dp[i][s][d] = max(cur, second); } else { auto it = lower_bound(sorted.begin(), sorted.end(), nums[i] - D); int el = it == sorted.end()? 1e18: *it; int co = coord[el]; int cur; if (co == 0) cur = 1; else { cur = query(segtree1, 0, co - 1) + 1; } int curco = coord[nums[i]]; int second; if (curco == 0) second = 1; else { second = query(segtree2, 0, curco - 1) + 1; } dp[i][s][d] = max(cur, second); } } upd(segtree0, coord[nums[i]], dp[i][0][d]); upd(segtree1, coord[nums[i]], dp[i][1][d]); upd(segtree2, coord[nums[i]], dp[i][2][d]); } } int ans = 0; forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]); out(ans); //} }

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

glo.cpp: In function 'int main()':
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'n' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
glo.cpp:43:9: note: in expansion of macro 'get'
   43 |         get(n);
      |         ^~~
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
glo.cpp:44:9: note: in expansion of macro 'get'
   44 |         get(x);
      |         ^~~
glo.cpp:12:40: warning: unnecessary parentheses in declaration of 'nums' [-Wparentheses]
   12 | #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
      |                                        ^
glo.cpp:45:9: note: in expansion of macro 'getList'
   45 |         getList(n, nums);
      |         ^~~~~~~
glo.cpp:10:23: warning: unnecessary parentheses in declaration of 'a' [-Wparentheses]
   10 | #define get(name) int (name); cin >> (name)
      |                       ^
glo.cpp:12:76: note: in expansion of macro 'get'
   12 | #define getList(cnt, name) vector<int> (name); for (int _=0;_<(cnt);_++) { get(a); (name).push_back(a); }
      |                                                                            ^~~
glo.cpp:45:9: note: in expansion of macro 'getList'
   45 |         getList(n, nums);
      |         ^~~~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:51:9: note: in expansion of macro 'forto'
   51 |         forto(n, i) {
      |         ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:63:9: note: in expansion of macro 'forto'
   63 |         forto(2 * x + 1, d) {
      |         ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:64:13: note: in expansion of macro 'forto'
   64 |             forto(4 * m, i) {
      |             ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:71:13: note: in expansion of macro 'forto'
   71 |             forto(n, i) {
      |             ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 's' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:72:17: note: in expansion of macro 'forto'
   72 |                 forto(3, s) {
      |                 ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:119:9: note: in expansion of macro 'forto'
  119 |         forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
      |         ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 's' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:119:21: note: in expansion of macro 'forto'
  119 |         forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
      |                     ^~~~~
glo.cpp:15:35: warning: unnecessary parentheses in declaration of 'd' [-Wparentheses]
   15 | #define forto(name, var) for (int (var) = 0; (var) < (name); (var)++)
      |                                   ^
glo.cpp:119:33: note: in expansion of macro 'forto'
  119 |         forto(n, i) forto(3, s) forto(2 * x + 1, d) ans = max(ans, dp[i][s][d]);
      |                                 ^~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...