oj.uz

Submission #256443

# Submission time Handle Problem Language Result Execution time Memory
256443 2020-08-02T17:29:06 Z doowey Fire (JOI20_ho_t5) C++14
0 / 100
 1000 ms 14464 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;

int m;
int A[N];
int L[N];
int R[N];

const int M = (int)1e6 + 100;
ll tree[M];

void innit(){
    for(int i = 0 ; i < M; i ++ ){
        tree[i] = 0;
    }
}

void upd(int id, ll v){
    id += m;
    tree[id] += v;
    id /= 2;
    while(id > 0){
        tree[id] = tree[id * 2] + tree[id * 2 + 1];
        id /= 2;
    }
}

ll qry(int l, int r){
    l += m;
    r += m;
    ll res = 0;
    while(l <= r){
        if(l % 2 == 1) res += tree[l ++ ];
        if(r % 2 == 0) res += tree[r -- ];
        l /= 2;
        r /= 2;
    }
    return res;
}

struct Q{
    int lef;
    int rig;
    int idx;
};

vector<Q> typ[N];
ll ans[N];
vector<Q> eve[N];
vector<pii> lin[N];

int main(){
    fastIO;
    freopen("in.txt", "r", stdin);
    int n, q;
    cin >> n >> q;
    m = n * 2 + 10;
    for(int i = 1; i <= n; i ++ ){
        cin >> A[i];
    }
    int tt, li, ri;
    for(int qq = 0; qq < q; qq ++ ){
        cin >> tt >> li >> ri;
        typ[tt].push_back({li, ri, qq});
    }
    vector<int> id;
    for(int i = 1; i <= n; i ++ ){
        while(!id.empty() && A[id.back()] <= A[i]){
            R[id.back()] = i;
            id.pop_back();
        }
        if(id.empty()){
            L[i] = i-n;
        }
        else{
            L[i] = id.back();
        }
        id.push_back(i);
    }
    for(int i = 1; i <= n; i ++ ){
        if(R[i] == 0)
            R[i] = i+n;
    }
    int len;
    for(int i = 1; i <= n; i ++ ){
        if(i - L[i] < R[i] - i){
            len = R[i] - i;
            for(int j = 0; j < i - L[i]; j ++ ){
                eve[j].push_back({i, j, A[i]});
                if(j + len <= n)
                    eve[j + len].push_back({i + len, j + len, -A[i]});
            }
        }
        else{
            len = i - L[i];
            for(int j = 0 ; j < R[i] - i; j ++){
                lin[j].push_back(mp(i + j, A[i]));
                if(j + len <= n)
                    lin[j + len].push_back(mp(i + j, -A[i]));
            }
        }
    }
    innit();
    for(int t = 0; t <= n; t ++ ){
        for(auto q : eve[t]){
            upd(q.lef - t + n, q.idx);
        }
        for(auto q : typ[t]){
            ans[q.idx] += qry(q.lef - t + n, q.rig - t + n);
        }
    }
    innit();
    for(int t = 0; t <= n; t ++ ){
        for(auto q : lin[t]){
            upd(q.fi, q.se);
        }
        for(auto q : typ[t]){
            ans[q.idx] += qry(q.lef, q.rig);
        }
    }
    for(int t =0 ; t < q ;t ++ )
        cout << ans[t] << "\n";
    return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("in.txt", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14464 KB Time limit exceeded

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14464 KB Time limit exceeded

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14464 KB Time limit exceeded

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 14464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 14464 KB Time limit exceeded