oj.uz

답안 #743691

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
743691 2023-05-17T17:40:34 Z KG07 Pilot (NOI19_pilot) C++14
26 / 100
 1000 ms 13204 KB 
// 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -