oj.uz

Submission #153706

# Submission time Handle Problem Language Result Execution time Memory
153706 2019-09-15T09:17:22 Z AlexLuchianov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
64 / 100
 3000 ms 113204 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 1000000;
int v[1 + nmax];

vector<pair<int,int>> querys[1 + nmax];
vector<pair<int,int>> interval[1 + nmax];

int sol[1 + nmax];
int key[1 + nmax];

int aint[1 + nmax * 4];

void update(int node, int from, int to, int x, int val){
  if(from < to){
    int mid = (from + to) / 2;
    if(x <= mid)
      update(node * 2 , from, mid, x, val);
    else
      update(node * 2 + 1, mid + 1 , to, x, val);
    aint[node] = MAX(aint[node * 2], aint[node * 2 + 1]);
  } else
    aint[node] = MAX(aint[node], val);
}

int query(int node,int from, int to, int x, int y){
  if(from == x && to == y)
    return aint[node];
  else{
    int mid = (from + to) / 2;
    int result1 = 0, result2 = 0;
    if(x <= mid)
      result1 = query(node * 2, from, mid, x, MIN(y, mid));
    if(mid + 1 <= y)
      result2 = query(node * 2 + 1, mid + 1, to, MAX(mid + 1, x), y);
    return MAX(result1, result2);
  }
}

int main()
{
  int n, m;
  cin >> n >> m;
  stack<int> st;
  for(int i = 1; i <= n; i++) {
    cin >> v[i];
    while(0 < st.size() && v[st.top()] <= v[i])
      st.pop();
    if(0 < st.size())
      interval[i].push_back({st.top(), v[st.top()] + v[i]});
    st.push(i);
  }

  for(int i = 1;i <= m; i++){
    int x, y;
    cin >> x >> y >> key[i];
    querys[y].push_back({x, i});
  }

  for(int i = 1;i <= n; i++){
    for(int h = 0; h < interval[i].size(); h++)
      update(1, 1, n, interval[i][h].first, interval[i][h].second);
    for(int h = 0; h < querys[i].size(); h++)
      sol[querys[i][h].second] = query(1, 1, n, querys[i][h].first , i);
 }

  for(int i = 1;i <= m; i++)
    cout << (sol[i] <= key[i]) << '\n';
  return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:70:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < interval[i].size(); h++)
                    ~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int h = 0; h < querys[i].size(); h++)
                    ~~^~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 48 ms 47480 KB Output is correct
4 Correct 47 ms 47244 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 48 ms 47292 KB Output is correct
7 Correct 48 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 48 ms 47352 KB Output is correct
10 Correct 48 ms 47336 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 48 ms 47480 KB Output is correct
4 Correct 47 ms 47244 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 48 ms 47292 KB Output is correct
7 Correct 48 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 48 ms 47352 KB Output is correct
10 Correct 48 ms 47336 KB Output is correct
11 Correct 53 ms 47480 KB Output is correct
12 Correct 58 ms 47736 KB Output is correct
13 Correct 57 ms 47736 KB Output is correct
14 Correct 73 ms 47804 KB Output is correct
15 Correct 73 ms 47804 KB Output is correct
16 Correct 59 ms 47600 KB Output is correct
17 Correct 67 ms 47608 KB Output is correct
18 Correct 58 ms 47732 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 55944 KB Output is correct
2 Correct 315 ms 56296 KB Output is correct
3 Correct 294 ms 52344 KB Output is correct
4 Correct 297 ms 52472 KB Output is correct
5 Correct 303 ms 52532 KB Output is correct
6 Correct 267 ms 52088 KB Output is correct
7 Correct 269 ms 51920 KB Output is correct
8 Correct 281 ms 54488 KB Output is correct
9 Correct 194 ms 50748 KB Output is correct
10 Correct 277 ms 54128 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 48 ms 47480 KB Output is correct
4 Correct 47 ms 47244 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 48 ms 47292 KB Output is correct
7 Correct 48 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 48 ms 47352 KB Output is correct
10 Correct 48 ms 47336 KB Output is correct
11 Correct 53 ms 47480 KB Output is correct
12 Correct 58 ms 47736 KB Output is correct
13 Correct 57 ms 47736 KB Output is correct
14 Correct 73 ms 47804 KB Output is correct
15 Correct 73 ms 47804 KB Output is correct
16 Correct 59 ms 47600 KB Output is correct
17 Correct 67 ms 47608 KB Output is correct
18 Correct 58 ms 47732 KB Output is correct
19 Correct 823 ms 68852 KB Output is correct
20 Correct 782 ms 68744 KB Output is correct
21 Correct 738 ms 67456 KB Output is correct
22 Correct 737 ms 67436 KB Output is correct
23 Correct 728 ms 67408 KB Output is correct
24 Correct 667 ms 58940 KB Output is correct
25 Correct 682 ms 59052 KB Output is correct
26 Correct 713 ms 59608 KB Output is correct
27 Correct 784 ms 59544 KB Output is correct
28 Correct 764 ms 59732 KB Output is correct
29 Correct 725 ms 60568 KB Output is correct
30 Correct 726 ms 60456 KB Output is correct
31 Correct 735 ms 60336 KB Output is correct
32 Correct 731 ms 60448 KB Output is correct
33 Correct 746 ms 60644 KB Output is correct
34 Correct 655 ms 58500 KB Output is correct
35 Correct 648 ms 58640 KB Output is correct
36 Correct 632 ms 58436 KB Output is correct
37 Correct 632 ms 58384 KB Output is correct
38 Correct 653 ms 58712 KB Output is correct
39 Correct 650 ms 61532 KB Output is correct
40 Correct 534 ms 58544 KB Output is correct
41 Correct 595 ms 62040 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 47352 KB Output is correct
2 Correct 52 ms 47484 KB Output is correct
3 Correct 48 ms 47480 KB Output is correct
4 Correct 47 ms 47244 KB Output is correct
5 Correct 47 ms 47352 KB Output is correct
6 Correct 48 ms 47292 KB Output is correct
7 Correct 48 ms 47352 KB Output is correct
8 Correct 48 ms 47352 KB Output is correct
9 Correct 48 ms 47352 KB Output is correct
10 Correct 48 ms 47336 KB Output is correct
11 Correct 53 ms 47480 KB Output is correct
12 Correct 58 ms 47736 KB Output is correct
13 Correct 57 ms 47736 KB Output is correct
14 Correct 73 ms 47804 KB Output is correct
15 Correct 73 ms 47804 KB Output is correct
16 Correct 59 ms 47600 KB Output is correct
17 Correct 67 ms 47608 KB Output is correct
18 Correct 58 ms 47732 KB Output is correct
19 Execution timed out 3031 ms 113204 KB Time limit exceeded
20 Halted 0 ms 0 KB -