oj.uz

Submission #259035

# Submission time Handle Problem Language Result Execution time Memory
259035 2020-08-07T04:55:38 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 = 2000;
    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 0 ms 384 KB Output is correct
6 Correct 0 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 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 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 4 ms 384 KB Output is correct
4 Correct 20 ms 508 KB Output is correct
5 Correct 66 ms 512 KB Output is correct
6 Correct 101 ms 640 KB Output is correct
7 Correct 118 ms 760 KB Output is correct
8 Correct 68 ms 700 KB Output is correct
9 Correct 73 ms 640 KB Output is correct
10 Correct 174 ms 640 KB Output is correct
11 Correct 175 ms 760 KB Output is correct
12 Correct 168 ms 760 KB Output is correct
13 Correct 175 ms 760 KB Output is correct
14 Correct 149 ms 760 KB Output is correct
15 Correct 169 ms 760 KB Output is correct
16 Correct 82 ms 760 KB Output is correct
17 Correct 25 ms 648 KB Output is correct
18 Correct 200 ms 760 KB Output is correct
19 Correct 178 ms 760 KB Output is correct
20 Correct 190 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 1 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 37 ms 2300 KB Output is correct
13 Correct 62 ms 3056 KB Output is correct
14 Correct 89 ms 5228 KB Output is correct
15 Correct 119 ms 6628 KB Output is correct
16 Correct 86 ms 6256 KB Output is correct
17 Correct 39 ms 3056 KB Output is correct
18 Correct 70 ms 4836 KB Output is correct
19 Correct 86 ms 7148 KB Output is correct
20 Correct 42 ms 4976 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 1016 KB Output is correct
2 Correct 697 ms 1396 KB Output is correct
3 Correct 1478 ms 2036 KB Output is correct
4 Correct 2250 ms 2852 KB Output is correct
5 Correct 2979 ms 3204 KB Output is correct
6 Correct 3380 ms 3680 KB Output is correct
7 Correct 2501 ms 4440 KB Output is correct
8 Correct 1517 ms 5100 KB Output is correct
9 Correct 861 ms 5504 KB Output is correct
10 Correct 304 ms 5740 KB Output is correct
11 Correct 1262 ms 5728 KB Output is correct
12 Correct 3290 ms 5740 KB Output is correct
13 Execution timed out 4083 ms 4716 KB Time limit exceeded
14 Halted 0 ms 0 KB -