Submission #516373

#	Time	Username	Problem	Language	Result	Execution time	Memory
516373		Jomnoi	Pilot (NOI19_pilot)	C++17	100 / 100	746 ms	80612 KiB

pilot

#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;

const int N = 1e6 + 10;
const int MAX_H = 1e6;

vector <int> Q[N];
bool visited[N];
int parent[N];
int sz[N];
long long qs[N];

int root(int u) {
    if(u == parent[u]) {
        return u;
    }
    return parent[u] = root(parent[u]);
}

long long cal(int x) {
    return 1ll * x * (x + 1) / 2;
}

int main() {
    int n, q;
    scanf(" %d %d", &n, &q);
    for(int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    for(int i = 1; i <= n; i++) {
        int h;
        scanf(" %d", &h);
        Q[h].push_back(i);
    }
    
    for(int h = 1; h <= MAX_H; h++) {
        qs[h] = qs[h - 1];
        for(auto i : Q[h]) {
            visited[i] = true;
            qs[h]++;
            if(visited[i - 1] == true) {
                int u = root(i), v = root(i - 1);
                qs[h] -= cal(sz[u]) + cal(sz[v]);

                if(sz[u] < sz[v]) {
                    swap(u, v);
                }
                sz[u] += sz[v];
                parent[v] = u;
                qs[h] += cal(sz[u]);
            }
            if(visited[i + 1] == true) {
                int u = root(i), v = root(i + 1);
                qs[h] -= cal(sz[u]) + cal(sz[v]);

                if(sz[u] < sz[v]) {
                    swap(u, v);
                }
                sz[u] += sz[v];
                parent[v] = u;
                qs[h] += cal(sz[u]);
            }
        }
    }

    while(q--) {
        int y;
        scanf(" %d", &y);
        printf("%lld\n", qs[y]);
    }
    return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     scanf(" %d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
pilot.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf(" %d", &h);
      |         ~~~~~^~~~~~~~~~~
pilot.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |         scanf(" %d", &y);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11