Submission #743691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
743691	2023-05-17T17:40:34 Z	KG07	Pilot (NOI19_pilot)	C++14	26 / 100	1000 ms	13204 KB

pilot

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
pair<int, int> a[2100000];
int h[1000001];
long long d[1000001];
priority_queue<pair<int, int>> q;
void L(int x, int y, bool z){
    int x_ = x, y_ = y;
    if(!z){
        x_ = 0;
        y_ = 0;
    }
    while(x != y){
        if(x % 2 == 1){
            a[x].first = x_;
            a[x].second = y_;
            x++;
        }
        if(y % 2 == 0){
            a[y].first = x_;
            a[y].second = y_;
            y--;
        }
        x /= 2;
        y /= 2;
    }
    a[x].first = x_;
    a[y].second = y_;
}
int g(int x){
    while(!a[x].first){
        x /= 2;
    }
    return x;
}

int main() {
    // Write C++ code here
    int n, m;
    cin >> n >> m;
    int k = 1, o = 0;
    while(k < n){
        k *= 2;
    }
    for(int i = 0; i < n; i++){
        cin >> h[i];
        q.push({h[i], i});
        o = max(o, h[i]);
    }
    L(k, k+n-1, true);
    while(!q.empty()){
        int w = q.top().first;
        int z = q.top().second;
        q.pop();
        int t = g(k+z);
        int x = a[t].first, y = a[t].second;
        L(a[t].first, a[t].second, false);
        d[w] += 1ll * (k+z-x+1) * (y-k-z+1);
        if(k+z == x && k+z == y){
            continue;
        }
        if(k+z > x){
            L(x, k+z-1, true);
        }
        if(k+z < y){
            L(k+z+1, y, true);
        }
    }
    for(int i = o; i; i--){
        d[i-1] += d[i];
    }
    for(int i = 0; i < m; i++){
        int w;
        cin >> w;
        cout << 1ll * n * (n+1) / 2 - d[w+1] << "\n";
    }

    return 0;
}

Subtask #1
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1069 ms	212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #3
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1069 ms	212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #4
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1069 ms	212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1039 ms	2224 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	191 ms	5812 KB	Output is correct
2	Correct	202 ms	5864 KB	Output is correct
3	Correct	194 ms	5772 KB	Output is correct
4	Correct	203 ms	5992 KB	Output is correct
5	Correct	209 ms	5704 KB	Output is correct

Subtask #7
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	202 ms	13108 KB	Output is correct
2	Correct	233 ms	12976 KB	Output is correct
3	Correct	214 ms	12924 KB	Output is correct
4	Correct	224 ms	13204 KB	Output is correct
5	Correct	277 ms	13156 KB	Output is correct

Subtask #8
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1039 ms	2224 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #9
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1069 ms	212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Subtask #10
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	4120 KB	Output is correct
3	Correct	6 ms	7236 KB	Output is correct
4	Correct	1 ms	304 KB	Output is correct
5	Correct	6 ms	7348 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	5 ms	7764 KB	Output is correct
8	Correct	1 ms	312 KB	Output is correct
9	Correct	4 ms	5972 KB	Output is correct
10	Correct	1 ms	212 KB	Output is correct
11	Execution timed out	1069 ms	212 KB	Time limit exceeded
12	Halted	0 ms	0 KB	-

Submission #743691

Compilation message