oj.uz

Submission #13785

# Submission time Handle Problem Language Result Execution time Memory
13785 2015-04-01T10:22:42 Z gs14004 역사적 조사 (JOI14_historical) C++14
100 / 100
 2783 ms 6428 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
const int sz = 300;
 
struct q{int s,e,n;}qr[100005];
bool cmp(q a, q b){return a.s / sz == b.s / sz ? (a.e < b.e) : (a.s < b.s);}
 
int a[100005],n,q;
vector<int> p;
long long res[100005];
int lim;
 
inline void add(int pos, int val, long long* tree){
    pos += lim;
    tree[pos] += 1ll * val * p[pos-lim];
    while(pos > 1){
        pos >>= 1;
        tree[pos] = max(tree[2*pos],tree[2*pos+1]);
    }
}
 
inline void solve(){
    long long tree[270000] = {};
    for(lim = 1; lim <= p.size(); lim <<= 1);
    int s = 1, e = 0;
    for (int i=0; i<q; i++) {
        while (s < qr[i].s) {
            add(a[s],-1,tree);
            s++;
        }
        while (qr[i].s < s) {
            s--;
            add(a[s],1,tree);
        }
        while (e < qr[i].e) {
            e++;
            add(a[e],1,tree);
        }
        while (qr[i].e < e) {
            add(a[e],-1,tree);
            e--;
        }
        res[qr[i].n] = tree[1];
    }
}
 
int main(){
    scanf("%d %d",&n,&q);
    for (int i=1; i<=n; i++) {
        scanf("%d",&a[i]);
        p.push_back(a[i]);
    }
    for (int i=0; i<q; i++) {
        scanf("%d %d",&qr[i].s,&qr[i].e);
        qr[i].n = i;
    }
    sort(qr,qr+q,cmp);
    sort(p.begin(),p.end());
    p.resize(unique(p.begin(),p.end()) - p.begin());
    for (int i=1; i<=n; i++) {
        a[i] = (int)(lower_bound(p.begin(),p.end(),a[i]) - p.begin());
    }
    solve();
    for (int i=0; i<q; i++) {
        printf("%lld\n",res[i]);
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5912 KB Output is correct
2 Correct 0 ms 5904 KB Output is correct
3 Correct 0 ms 5904 KB Output is correct
4 Correct 6 ms 5912 KB Output is correct
5 Correct 12 ms 5908 KB Output is correct
6 Correct 17 ms 5908 KB Output is correct
7 Correct 18 ms 5904 KB Output is correct
8 Correct 14 ms 5912 KB Output is correct
9 Correct 14 ms 5908 KB Output is correct
10 Correct 20 ms 5912 KB Output is correct
11 Correct 24 ms 5908 KB Output is correct
12 Correct 24 ms 5908 KB Output is correct
13 Correct 24 ms 5912 KB Output is correct
14 Correct 23 ms 5912 KB Output is correct
15 Correct 19 ms 5908 KB Output is correct
16 Correct 12 ms 5908 KB Output is correct
17 Correct 8 ms 5912 KB Output is correct
18 Correct 17 ms 5908 KB Output is correct
19 Correct 24 ms 5912 KB Output is correct
20 Correct 26 ms 5908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5912 KB Output is correct
2 Correct 0 ms 5912 KB Output is correct
3 Correct 0 ms 5908 KB Output is correct
4 Correct 0 ms 5912 KB Output is correct
5 Correct 0 ms 5912 KB Output is correct
6 Correct 0 ms 5908 KB Output is correct
7 Correct 4 ms 5908 KB Output is correct
8 Correct 7 ms 5904 KB Output is correct
9 Correct 14 ms 6044 KB Output is correct
10 Correct 4 ms 6168 KB Output is correct
11 Correct 78 ms 6424 KB Output is correct
12 Correct 37 ms 6424 KB Output is correct
13 Correct 48 ms 6428 KB Output is correct
14 Correct 82 ms 6420 KB Output is correct
15 Correct 126 ms 6420 KB Output is correct
16 Correct 80 ms 6420 KB Output is correct
17 Correct 45 ms 6424 KB Output is correct
18 Correct 66 ms 6420 KB Output is correct
19 Correct 84 ms 6428 KB Output is correct
20 Correct 50 ms 6424 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 5912 KB Output is correct
2 Correct 115 ms 6044 KB Output is correct
3 Correct 267 ms 6044 KB Output is correct
4 Correct 469 ms 6168 KB Output is correct
5 Correct 691 ms 6172 KB Output is correct
6 Correct 774 ms 6168 KB Output is correct
7 Correct 739 ms 6424 KB Output is correct
8 Correct 644 ms 6420 KB Output is correct
9 Correct 513 ms 6424 KB Output is correct
10 Correct 389 ms 6420 KB Output is correct
11 Correct 693 ms 6420 KB Output is correct
12 Correct 1198 ms 6420 KB Output is correct
13 Correct 1862 ms 6424 KB Output is correct
14 Correct 2524 ms 6428 KB Output is correct
15 Correct 2783 ms 6420 KB Output is correct
16 Correct 2752 ms 6420 KB Output is correct
17 Correct 2734 ms 6424 KB Output is correct
18 Correct 2726 ms 6420 KB Output is correct
19 Correct 2706 ms 6424 KB Output is correct
20 Correct 2520 ms 6420 KB Output is correct
21 Correct 2516 ms 6428 KB Output is correct
22 Correct 2494 ms 6424 KB Output is correct
23 Correct 2484 ms 6424 KB Output is correct
24 Correct 2490 ms 6424 KB Output is correct
25 Correct 273 ms 6424 KB Output is correct