oj.uz

Submission #868502

# Submission time Handle Problem Language Result Execution time Memory
868502 2023-10-31T15:03:40 Z hqminhuwu Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
0 / 100
 52 ms 38292 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int bit[N],n;
void update (int u, int val){
    for (; u > 0; u -= u & -u)
        bit[u] = max (bit[u],val);
}

int get (int u){
    int res = 0;
    for (; u <= n; u += u & -u)
        res = max (res,bit[u]);
    return res;
}

stack <int> s;
int q,i,a[N],u,v,h[N],ans[N];
vector <pii> g[N];
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    forr (i,1,n)
        cin >> a[i];
    forr (i,1,q){
        cin >> u >> v;
        cin >> h[i];
        g[v].pb({i,u});
    }
    
    forr (i,1,n){
        while (!s.empty() && a[i] >= a[s.top()])
            s.pop();
        if (!s.empty())
            update(s.top(),a[i] + a[s.top()]);
        s.push(i);
        for (pii w : g[i])
            ans[w.st] = get(w.nd);
    }
    forr (i,1,q)
        cout << ans[i] << "\n";
    return 0;
}
/*



*/

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 38292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 21264 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 19036 KB Output isn't correct
2 Halted 0 ms 0 KB -