Submission #787573

#	Time	Username	Problem	Language	Result	Execution time	Memory
787573		RecursiveCo	Global Warming (CEOI18_glo)	C++14	45 / 100	1291 ms	262144 KiB

glo

// 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);
    //}
}

Compilation message (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]);
      |                                 ^~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 13
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25