Submission #1073503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073503		DeathIsAwe	Global Warming (CEOI18_glo)	C++17	100 / 100	209 ms	8124 KiB

glo

#include <bits/stdc++.h>
using namespace std;
pair<int,int> segment[524288];


void update(int a, int b, int val, int time) {
    a += 262144; b += 262144;
    while (a <= b) {
        if (a % 2 == 1) {segment[a++] = make_pair(val, time);}
        if (b % 2 == 0) {segment[b--] = make_pair(val, time);}
        a /= 2; b /= 2;
    }
}


int fetch(int a) {
    int pow2 = 131072;
    int node = 1;
    pair<int,int> ans = segment[node];
    while (pow2 > 0) {
        node *= 2;
        if (a >= pow2) {
            a -= pow2; 
            node++;
        }
        if (ans.second < segment[node].second) {
            ans.first = segment[node].first; ans.second = segment[node].second;
        }
        pow2 /= 2;
    }
    return ans.first;
}


bool comp(int a, int b) {
    return fetch(a) < fetch(b);
}


int main() {
    for (int i=0;i<524288;i++) {
        segment[i] = make_pair(0, -2);
    }
    int n, x; cin >> n >> x;
    vector<int> arr(n);
    for (int i=0;i<n;i++) {
        cin >> arr[i];
        segment[i + 262144] = make_pair(arr[i], -1);
    }


    vector<int> lisnormal;
    vector<int> dum;
    int pos1, pos2;
    for (int i=0;i<n;i++) {
        pos1 = lower_bound(lisnormal.begin(), lisnormal.end(), arr[i] + x) - lisnormal.begin();
        segment[524287] = make_pair(arr[i] + x, i);
        pos2 = lower_bound(dum.begin() ,dum.end(), 524287, comp) - dum.begin();
        update(pos2, max(pos2, pos1), arr[i] + x, i);
        while (dum.size() <= max(pos2, pos1)) {
            dum.push_back(dum.size());
        }
        pos1 = lower_bound(lisnormal.begin(), lisnormal.end(), arr[i]) - lisnormal.begin();
        if (pos1 == lisnormal.size()) {
            lisnormal.push_back(arr[i]);
        } else {
            lisnormal[pos1] = arr[i];
        }
        //for (int j: lisnormal) {
        //    cout << j << ' ';
        //} cout << '\n';
        //for (int j: dum) {
        //    cout << fetch(j) << ' ';
        //} cout << '\n' << '\n' << '\n';
    }
    cout << dum.size();
}

Compilation message (stderr)

glo.cpp: In function 'int main()':
glo.cpp:60:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'const int' [-Wsign-compare]
   60 |         while (dum.size() <= max(pos2, pos1)) {
      |                ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
glo.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         if (pos1 == lisnormal.size()) {
      |             ~~~~~^~~~~~~~~~~~~~~~~~~

• 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