oj.uz

Submission #952783

# Submission time Handle Problem Language Result Execution time Memory
952783 2024-03-24T19:29:59 Z idiotcomputer Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++11
0 / 100
 691 ms 81468 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define f first 
#define s second

const int mxN = 1e6;

int n;
int bit[mxN+1];

void upd(int x, int v){
    if (x == 0) return;
    while (x <= n){
      //  cout << x << '\n';
        bit[x] = max(bit[x],v);
        x += ((~x+1) & x);
    }
}

int query(int x){
    int res = 0;
    while (x > 0){
       // cout << x << '\n';
        res = max(res,bit[x]);
        x -= ((~x+1) & x);
    }
    return res;
}

struct qu {
    int l,r,k,idx;
};

int main()
{
    memset(bit,0,sizeof(bit));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int m;
    cin >> n >> m;
    
    int vals[n+1];
    vector<qu> all[n+1];
    for (int i =1; i <= n; i++) cin >> vals[i];
    vals[0] = 1e9+1;
    
    bitset<mxN> ans;
    qu temp;
    for (int i =0; i < m; i++){
        cin >> temp.l >> temp.r >> temp.k;
        temp.idx = i;
        all[temp.r].pb(temp);
    }
  //  cout << "Read\n";
    
    stack<int> curr;
    curr.push(0);
    for (int i = 1; i <= n; i++){
        while (vals[curr.top()] <= vals[i]) curr.pop();
        upd(curr.top(),vals[curr.top()]+vals[i]);
        curr.push(i);
        
        for (qu c : all[i]){
            ans[c.idx] = query(c.l) <= c.k;
        }
    }
    for (int i =0; i < m; i++) cout << ans[i] << "\n";
    
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 1 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -