Submission #145055

#	Time	Username	Problem	Language	Result	Execution time	Memory
145055		karma	Global Warming (CEOI18_glo)	C++11	100 / 100	525 ms	23012 KiB

glo

#include<bits/stdc++.h>
#define FileName      "test"
#define ll            long long
#define pb            emplace_back
#define mp            make_pair
#define x             first
#define y             second
//#define LuckyAurora
#pragma GCC optimization ("O3")

using namespace std;

const int N = 2e5 + 3;

int t[N], n, x, res = 0, pos, cur0, cur1;
vector<int> v;
struct TSegment {
    vector<int> l, h, st;
    TSegment() {}
    TSegment(int n) {l.resize(4 * n + 1), h.resize(4 * n + 1), st.resize(4 * n + 1);}
    void Build(int x, int low, int high)
    {
        l[x] = low, h[x] = high;
        if(l[x] == h[x]) {
            st[x] = 0;
            return;
        }
        int mid = (low + high) >> 1;
        Build(x << 1, low, mid);
        Build(x << 1 | 1, mid + 1, high);
    }
    void Update(int x, int pos, int val)
    {
         if(l[x] > pos || h[x] < pos) return;
         if(l[x] == h[x]) {
            st[x] = max(st[x], val);
            return;
         }
         Update(x << 1, pos, val);
         Update(x << 1 | 1, pos, val);
         st[x] = max(st[x << 1], st[x << 1 | 1]);
    }
    int Query(int x, int low, int high)
    {
        if(l[x] > high || h[x] < low) return 0;
        if(l[x] >= low && h[x] <= high) return st[x];
        return max(Query(x << 1, low, high), Query(x << 1 | 1, low, high));
    }
} f0, f1;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin >> n >> x;
    for(int i = 1; i <= n; ++i) cin >> t[i], v.pb(t[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    f0 = TSegment(int(v.size()));
    f1 = TSegment(int(v.size()));
    f0.Build(1, 1, int(v.size()));
    f1.Build(1, 1, int(v.size()));
    for(int i = 1; i <= n; ++i) {
        pos = upper_bound(v.begin(), v.end(), t[i] + x - 1) - v.begin();
        t[i] = lower_bound(v.begin(), v.end(), t[i]) - v.begin();
        cur1 = cur0 = -1;
        if(t[i] >= 1) cur0 = f0.Query(1, 1, t[i]) + 1;
        else cur0 = 1;
        if(pos >= 1 && pos <= n) cur1 = f0.Query(1, 1, pos) + 1;
        if(t[i] >= 1) cur1 = max(cur1, f1.Query(1, 1, t[i]) + 1);
        else cur1 = max(cur1, 1);
        f0.Update(1, t[i] + 1, cur0);
        f1.Update(1, t[i] + 1, cur1);
        res = max({res, cur0, cur1});
    }
    cout << res;
}

Compilation message (stderr)

glo.cpp:9:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
glo.cpp: In function 'int main()':
glo.cpp:56:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.inp", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
glo.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("test.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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