oj.uz

Submission #259034

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

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 = 1000;
    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 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 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 1 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 4 ms 384 KB Output is correct
4 Correct 14 ms 512 KB Output is correct
5 Correct 33 ms 512 KB Output is correct
6 Correct 48 ms 640 KB Output is correct
7 Correct 54 ms 640 KB Output is correct
8 Correct 46 ms 640 KB Output is correct
9 Correct 37 ms 640 KB Output is correct
10 Correct 93 ms 648 KB Output is correct
11 Correct 80 ms 760 KB Output is correct
12 Correct 80 ms 760 KB Output is correct
13 Correct 78 ms 760 KB Output is correct
14 Correct 69 ms 760 KB Output is correct
15 Correct 74 ms 760 KB Output is correct
16 Correct 39 ms 760 KB Output is correct
17 Correct 14 ms 656 KB Output is correct
18 Correct 78 ms 760 KB Output is correct
19 Correct 85 ms 764 KB Output is correct
20 Correct 87 ms 764 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 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 69 ms 4964 KB Output is correct
12 Correct 35 ms 2300 KB Output is correct
13 Correct 61 ms 3052 KB Output is correct
14 Correct 93 ms 5228 KB Output is correct
15 Correct 122 ms 6764 KB Output is correct
16 Correct 90 ms 6284 KB Output is correct
17 Correct 42 ms 3052 KB Output is correct
18 Correct 70 ms 4844 KB Output is correct
19 Correct 94 ms 7148 KB Output is correct
20 Correct 41 ms 4976 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 1016 KB Output is correct
2 Correct 311 ms 1396 KB Output is correct
3 Correct 702 ms 2036 KB Output is correct
4 Correct 1141 ms 2928 KB Output is correct
5 Correct 1515 ms 3312 KB Output is correct
6 Correct 1606 ms 3696 KB Output is correct
7 Correct 1299 ms 4452 KB Output is correct
8 Correct 873 ms 5024 KB Output is correct
9 Correct 519 ms 5612 KB Output is correct
10 Correct 221 ms 5740 KB Output is correct
11 Correct 777 ms 5732 KB Output is correct
12 Correct 1961 ms 5732 KB Output is correct
13 Correct 3124 ms 5848 KB Output is correct
14 Correct 3945 ms 6312 KB Output is correct
15 Execution timed out 4070 ms 5740 KB Time limit exceeded
16 Halted 0 ms 0 KB -