oj.uz

Submission #259024

# Submission time Handle Problem Language Result Execution time Memory
259024 2020-08-07T04:28:49 Z 반딧불(#5071) 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 7140 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];
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(){
    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 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 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 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 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 2 ms 384 KB Output is correct
4 Correct 5 ms 512 KB Output is correct
5 Correct 14 ms 512 KB Output is correct
6 Correct 21 ms 640 KB Output is correct
7 Correct 25 ms 768 KB Output is correct
8 Correct 18 ms 640 KB Output is correct
9 Correct 16 ms 640 KB Output is correct
10 Correct 34 ms 648 KB Output is correct
11 Correct 36 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 30 ms 760 KB Output is correct
15 Correct 34 ms 760 KB Output is correct
16 Correct 19 ms 768 KB Output is correct
17 Correct 7 ms 768 KB Output is correct
18 Correct 31 ms 760 KB Output is correct
19 Correct 35 ms 760 KB Output is correct
20 Correct 36 ms 768 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 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 1 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 7 ms 768 KB Output is correct
9 Correct 14 ms 1024 KB Output is correct
10 Correct 9 ms 1408 KB Output is correct
11 Correct 73 ms 4972 KB Output is correct
12 Correct 37 ms 2300 KB Output is correct
13 Correct 64 ms 3056 KB Output is correct
14 Correct 90 ms 5232 KB Output is correct
15 Correct 120 ms 6628 KB Output is correct
16 Correct 91 ms 6252 KB Output is correct
17 Correct 38 ms 3056 KB Output is correct
18 Correct 73 ms 4840 KB Output is correct
19 Correct 95 ms 7140 KB Output is correct
20 Correct 47 ms 4976 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 1016 KB Output is correct
2 Correct 243 ms 1396 KB Output is correct
3 Correct 608 ms 1908 KB Output is correct
4 Correct 1030 ms 2800 KB Output is correct
5 Correct 1451 ms 3312 KB Output is correct
6 Correct 1665 ms 3684 KB Output is correct
7 Correct 1444 ms 4460 KB Output is correct
8 Correct 927 ms 5092 KB Output is correct
9 Correct 618 ms 5612 KB Output is correct
10 Correct 225 ms 5732 KB Output is correct
11 Correct 871 ms 5832 KB Output is correct
12 Correct 2206 ms 5860 KB Output is correct
13 Correct 3696 ms 5972 KB Output is correct
14 Execution timed out 4083 ms 5220 KB Time limit exceeded
15 Halted 0 ms 0 KB -