oj.uz

Submission #259022

# Submission time Handle Problem Language Result Execution time Memory
259022 2020-08-07T04:24:46 Z 반딧불(#5071) 역사적 조사 (JOI14_historical) C++17
15 / 100
 4000 ms 5888 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[100002];
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 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 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 0 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 684 KB Output is correct
9 Correct 18 ms 640 KB Output is correct
10 Correct 35 ms 640 KB Output is correct
11 Correct 44 ms 764 KB Output is correct
12 Correct 35 ms 756 KB Output is correct
13 Correct 33 ms 640 KB Output is correct
14 Correct 31 ms 640 KB Output is correct
15 Correct 33 ms 640 KB Output is correct
16 Correct 26 ms 640 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 38 ms 640 KB Output is correct
19 Correct 36 ms 756 KB Output is correct
20 Correct 37 ms 760 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 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 2 ms 384 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 16 ms 1020 KB Output is correct
10 Correct 11 ms 1404 KB Output is correct
11 Correct 84 ms 4968 KB Output is correct
12 Correct 42 ms 2296 KB Output is correct
13 Correct 67 ms 3056 KB Output is correct
14 Incorrect 100 ms 4968 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 876 KB Output is correct
2 Correct 237 ms 1372 KB Output is correct
3 Correct 580 ms 1908 KB Output is correct
4 Correct 991 ms 2828 KB Output is correct
5 Correct 1443 ms 3172 KB Output is correct
6 Correct 1656 ms 4156 KB Output is correct
7 Correct 1456 ms 4412 KB Output is correct
8 Correct 991 ms 4960 KB Output is correct
9 Correct 636 ms 5472 KB Output is correct
10 Correct 219 ms 5888 KB Output is correct
11 Correct 847 ms 5728 KB Output is correct
12 Correct 2341 ms 5736 KB Output is correct
13 Correct 3682 ms 5828 KB Output is correct
14 Execution timed out 4061 ms 5096 KB Time limit exceeded
15 Halted 0 ms 0 KB -