oj.uz

Submission #403347

# Submission time Handle Problem Language Result Execution time Memory
403347 2021-05-13T05:11:50 Z cpp219 Fire (JOI20_ho_t5) C++14
6 / 100
 386 ms 89608 KB 
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 2e5 + 16;
const ll Log2 = 19;
const ll inf = 1e9 + 7;
typedef pair<ll,ll> LL;
///Road to EF/M

ll s[N],n,Q,T,l,r,ans[N],pre[N],suf[N];

struct Query{
    ll l,r,id;
};
vector<Query> q[N];
vector<LL> f[N],g[N];
ll bit[N];

void upd(ll p,ll val){
    for (ll i = p;i < N;i += i & -i) bit[i] += val;
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}
stack<ll> st;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #define task "test"
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++) cin>>s[i];
    for (ll i = 1;i <= Q;i++){
        cin>>T>>l>>r;
        q[T].push_back({l,r,i});
    }
    for (ll i = 1;i <= n;i++){
        while(!st.empty() && s[st.top()] <= s[i]) st.pop();
        if (!st.empty()) pre[i] = st.top();
        st.push(i);
    }
    while(!st.empty()) st.pop();
    for (ll i = n;i > 0;i--){
        while(!st.empty() && s[st.top()] < s[i]) st.pop();
        if (!st.empty()) suf[i] = st.top();
        else suf[i] = n + 1;
        st.push(i);
    }
    for (ll i = 1;i <= n;i++){
        if (!pre[i] || i - pre[i] > suf[i] - i){
            for (ll j = i;j < suf[i];j++){
                f[j - i].push_back({j,s[i]});
                if (pre[i]) f[j - pre[i]].push_back({j,-s[i]});
            }
        }
        else{
            for (ll j = i;j > pre[i];j--){
                g[i - j].push_back({j,s[i]});
                g[suf[i] - j].push_back({j,-s[i]});
            }
        }
    }
    for (ll i = 0;i <= n;i++){
        for (auto j : f[i]) upd(j.fs,j.sc);
        for (auto j : q[i]) ans[j.id] += Get(j.r) - Get(j.l - 1);
    }
    memset(bit,0,sizeof(bit));
    for (ll i = 0;i <= n;i++){
        for (auto j : g[i]) upd(j.fs,j.sc);
        for (auto j : q[i]) ans[j.id] += Get(j.r) - Get(j.l - 1);
    }
    for (ll i = 1;i <= Q;i++) cout<<ans[i]<<"\n";
}

Compilation message

ho_t5.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization "O2"
      | 
ho_t5.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
ho_t5.cpp: In function 'int main()':
ho_t5.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Incorrect 12 ms 16020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Correct 293 ms 83964 KB Output is correct
3 Correct 306 ms 89608 KB Output is correct
4 Incorrect 298 ms 85808 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Incorrect 386 ms 87648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 37836 KB Output is correct
2 Correct 235 ms 42264 KB Output is correct
3 Correct 264 ms 42776 KB Output is correct
4 Correct 241 ms 42276 KB Output is correct
5 Correct 237 ms 42860 KB Output is correct
6 Correct 228 ms 41820 KB Output is correct
7 Correct 232 ms 42468 KB Output is correct
8 Correct 218 ms 42576 KB Output is correct
9 Correct 242 ms 42496 KB Output is correct
10 Correct 236 ms 42168 KB Output is correct
11 Correct 243 ms 42592 KB Output is correct
12 Correct 229 ms 42148 KB Output is correct
13 Correct 227 ms 42012 KB Output is correct
14 Correct 224 ms 42172 KB Output is correct

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15948 KB Output is correct
2 Incorrect 12 ms 16020 KB Output isn't correct
3 Halted 0 ms 0 KB -