oj.uz

Submission #259025

# Submission time Handle Problem Language Result Execution time Memory
259025 2020-08-07T04:40:00 Z 반딧불(#5071) 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 7004 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

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];
inline 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]);
}

inline void removeNum(ll x){
    update(1, 0, k-1, x, -v[x]);
}
inline 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(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    sqrtN = ceil(sqrt(n));
    for(int i=0; i<n; i++) cin >> arr[i];
    renumber();
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> 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++){
        cout << ans[i] << '\n';
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 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 1 ms 384 KB Output is correct
6 Correct 0 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 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 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 3 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 13 ms 512 KB Output is correct
6 Correct 21 ms 640 KB Output is correct
7 Correct 25 ms 640 KB Output is correct
8 Correct 16 ms 640 KB Output is correct
9 Correct 16 ms 640 KB Output is correct
10 Correct 34 ms 640 KB Output is correct
11 Correct 34 ms 760 KB Output is correct
12 Correct 33 ms 760 KB Output is correct
13 Correct 33 ms 760 KB Output is correct
14 Correct 31 ms 760 KB Output is correct
15 Correct 40 ms 760 KB Output is correct
16 Correct 17 ms 768 KB Output is correct
17 Correct 8 ms 640 KB Output is correct
18 Correct 32 ms 760 KB Output is correct
19 Correct 35 ms 760 KB Output is correct
20 Correct 36 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 1 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 6 ms 768 KB Output is correct
9 Correct 13 ms 1024 KB Output is correct
10 Correct 9 ms 1408 KB Output is correct
11 Correct 72 ms 4972 KB Output is correct
12 Correct 36 ms 2300 KB Output is correct
13 Correct 62 ms 3056 KB Output is correct
14 Correct 91 ms 5232 KB Output is correct
15 Correct 125 ms 6632 KB Output is correct
16 Correct 88 ms 6252 KB Output is correct
17 Correct 40 ms 3056 KB Output is correct
18 Correct 73 ms 4836 KB Output is correct
19 Correct 92 ms 7004 KB Output is correct
20 Correct 41 ms 4972 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 1016 KB Output is correct
2 Correct 248 ms 1396 KB Output is correct
3 Correct 583 ms 1908 KB Output is correct
4 Correct 1020 ms 2852 KB Output is correct
5 Correct 1447 ms 3200 KB Output is correct
6 Correct 1656 ms 3696 KB Output is correct
7 Correct 1426 ms 4436 KB Output is correct
8 Correct 995 ms 5084 KB Output is correct
9 Correct 600 ms 5612 KB Output is correct
10 Correct 208 ms 5732 KB Output is correct
11 Correct 855 ms 5740 KB Output is correct
12 Correct 2233 ms 5732 KB Output is correct
13 Correct 3702 ms 5872 KB Output is correct
14 Execution timed out 4053 ms 5100 KB Time limit exceeded
15 Halted 0 ms 0 KB -