oj.uz

Submission #259023

# Submission time Handle Problem Language Result Execution time Memory
259023 2020-08-07T04:26:00 Z 반딧불(#5071) 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 7144 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")

using namespace std;

typedef long long ll;
int sqrtN;

struct Query{
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}

    bool operator<(const Query &tmp)const{
        if(l/sqrtN != tmp.l/sqrtN) return l < tmp.l;
        return r < tmp.r;
    }
};

int n, q, k;
ll arr[100002];
vector<Query> vec;
ll cnt[100002];
ll ans[100002];
vector<ll> v;

ll tree[400002];
void update(int i, int l, int r, int idx, ll val){
    if(l==r){
        tree[i] += val;
        return;
    }
    int m = (l+r)>>1;
    if(idx<=m) update(i*2, l, m, idx, val);
    else update(i*2+1, m+1, r, idx, val);
    tree[i] = max(tree[i*2], tree[i*2+1]);
}

void removeNum(ll x){
    update(1, 0, k-1, x, -v[x]);
}
void addNum(ll x){
    update(1, 0, k-1, x, v[x]);
}

void renumber(){
    for(int i=0; i<n; i++) v.push_back(arr[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0; i<n; i++) arr[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
    k = (int)v.size();
}

int main(){
    scanf("%d %d", &n, &q);
    sqrtN = ceil(sqrt(n));
    for(int i=0; i<n; i++) scanf("%lld", &arr[i]);
    renumber();
    for(int i=1; i<=q; i++){
        int l, r;
        scanf("%d %d", &l, &r);
        l--, r--;
        vec.push_back(Query(l, r, i));
    }
    sort(vec.begin(), vec.end());

    int s = 0, e = -1;
    for(int i=0; i<q; i++){
        Query tmp = vec[i];
        int l = tmp.l, r = tmp.r, idx = tmp.idx;
        while(e < r) addNum(arr[++e]);
        while(s > l) addNum(arr[--s]);
        while(e > r) removeNum(arr[e--]);
        while(s < l) removeNum(arr[s++]);
        ans[idx] = tree[1];
    }

    for(int i=1; i<=q; i++){
        printf("%lld\n", ans[i]);
    }
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:58:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=0; i<n; i++) scanf("%lld", &arr[i]);
                            ~~~~~^~~~~~~~~~~~~~~~~
historic.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l, &r);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 13 ms 512 KB Output is correct
6 Correct 22 ms 640 KB Output is correct
7 Correct 25 ms 640 KB Output is correct
8 Correct 17 ms 640 KB Output is correct
9 Correct 17 ms 640 KB Output is correct
10 Correct 35 ms 760 KB Output is correct
11 Correct 35 ms 640 KB Output is correct
12 Correct 34 ms 756 KB Output is correct
13 Correct 33 ms 760 KB Output is correct
14 Correct 31 ms 640 KB Output is correct
15 Correct 34 ms 640 KB Output is correct
16 Correct 19 ms 768 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 32 ms 640 KB Output is correct
19 Correct 35 ms 756 KB Output is correct
20 Correct 37 ms 760 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 15 ms 1020 KB Output is correct
10 Correct 9 ms 1404 KB Output is correct
11 Correct 81 ms 5096 KB Output is correct
12 Correct 39 ms 2296 KB Output is correct
13 Correct 68 ms 3048 KB Output is correct
14 Correct 100 ms 5224 KB Output is correct
15 Correct 137 ms 6632 KB Output is correct
16 Correct 104 ms 6252 KB Output is correct
17 Correct 45 ms 3052 KB Output is correct
18 Correct 76 ms 4832 KB Output is correct
19 Correct 86 ms 7144 KB Output is correct
20 Correct 44 ms 4932 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 952 KB Output is correct
2 Correct 233 ms 1368 KB Output is correct
3 Correct 579 ms 1904 KB Output is correct
4 Correct 999 ms 2704 KB Output is correct
5 Correct 1436 ms 3172 KB Output is correct
6 Correct 1649 ms 3684 KB Output is correct
7 Correct 1415 ms 4532 KB Output is correct
8 Correct 945 ms 5096 KB Output is correct
9 Correct 590 ms 5480 KB Output is correct
10 Correct 215 ms 5736 KB Output is correct
11 Correct 901 ms 5736 KB Output is correct
12 Correct 2243 ms 5708 KB Output is correct
13 Correct 3620 ms 5828 KB Output is correct
14 Execution timed out 4038 ms 5216 KB Time limit exceeded
15 Halted 0 ms 0 KB -