oj.uz

Submission #231036

# Submission time Handle Problem Language Result Execution time Memory
231036 2020-05-12T12:19:03 Z JooDdae 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 12408 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define mid ((l+r)>>1)
struct query{
    int l, r, id;
    bool operator < (const query &o) const{
        return make_pair(l>>9, r) < make_pair(o.l>>9, o.r);
    }
}q[100100];
int n, m, cnt, id[100100];
ll x[100100], tree[400400], ans[100100];
map<ll, int> mp;

void update(int id, ll val, int node = 1, int l = 1, int r = cnt){
    if(id < l || r < id) return;
    if(l == r){
        tree[node] += val;
        return;
    }
    update(id, val, node*2, l, mid), update(id, val, node*2+1, mid+1, r);
    tree[node] = max(tree[node*2], tree[node*2+1]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++) cin >> x[i], mp[x[i]] = 0;
    for(auto &x : mp) x.second = ++cnt;
    for(int i=1;i<=n;i++) id[i] = mp[x[i]];

    for(int i=1;i<=m;i++) cin >> q[i].l >> q[i].r, q[i].id = i;
    sort(q+1, q+1+m);
    
    int l = 1, r = 0;
    for(int i=1;i<=m;i++){
        while(l > q[i].l) l--, update(id[l], x[l]);
        while(r < q[i].r) r++, update(id[r], x[r]);
        while(l < q[i].l) update(id[l], -x[l]), l++;
        while(r > q[i].r) update(id[r], -x[r]), r--;

        ans[q[i].id] = tree[1];
    }
    for(int i=1;i<=m;i++) cout << ans[i] << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 13 ms 384 KB Output is correct
4 Correct 23 ms 512 KB Output is correct
5 Correct 49 ms 632 KB Output is correct
6 Correct 69 ms 760 KB Output is correct
7 Correct 79 ms 640 KB Output is correct
8 Correct 58 ms 640 KB Output is correct
9 Correct 56 ms 640 KB Output is correct
10 Correct 105 ms 768 KB Output is correct
11 Correct 106 ms 768 KB Output is correct
12 Correct 104 ms 768 KB Output is correct
13 Correct 101 ms 768 KB Output is correct
14 Correct 92 ms 768 KB Output is correct
15 Correct 102 ms 760 KB Output is correct
16 Correct 61 ms 640 KB Output is correct
17 Correct 24 ms 640 KB Output is correct
18 Correct 95 ms 760 KB Output is correct
19 Correct 108 ms 768 KB Output is correct
20 Correct 113 ms 1052 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 8 ms 640 KB Output is correct
8 Correct 12 ms 896 KB Output is correct
9 Correct 26 ms 1400 KB Output is correct
10 Correct 13 ms 1152 KB Output is correct
11 Correct 63 ms 3960 KB Output is correct
12 Correct 47 ms 1656 KB Output is correct
13 Correct 81 ms 2812 KB Output is correct
14 Correct 123 ms 6648 KB Output is correct
15 Correct 160 ms 9208 KB Output is correct
16 Correct 143 ms 11512 KB Output is correct
17 Correct 41 ms 2424 KB Output is correct
18 Correct 65 ms 3832 KB Output is correct
19 Correct 112 ms 12408 KB Output is correct
20 Correct 83 ms 10616 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 888 KB Output is correct
2 Correct 418 ms 1424 KB Output is correct
3 Correct 944 ms 2168 KB Output is correct
4 Correct 1524 ms 3196 KB Output is correct
5 Correct 2087 ms 3912 KB Output is correct
6 Correct 2357 ms 4600 KB Output is correct
7 Correct 2113 ms 4856 KB Output is correct
8 Correct 1599 ms 5636 KB Output is correct
9 Correct 1067 ms 6392 KB Output is correct
10 Correct 405 ms 6392 KB Output is correct
11 Correct 1489 ms 6392 KB Output is correct
12 Correct 3409 ms 6596 KB Output is correct
13 Execution timed out 4059 ms 6008 KB Time limit exceeded
14 Halted 0 ms 0 KB -