oj.uz

Submission #162748

# Submission time Handle Problem Language Result Execution time Memory
162748 2019-11-09T15:48:59 Z abacaba Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
8 / 100
 3000 ms 236292 KB 
#include <chrono>
#include <random>
#include <iostream>
#include <string>
#include <unordered_map>
#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
using namespace std;

#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e6 + 15;
int n, m, a[N], maxx[N << 2];
vector <int> t[N << 2];

void build(int v, int tl, int tr) {
    if(tl == tr) {
        t[v] = {a[tl]};
        return;
    }
    int mid = tl + tr >> 1, l = v << 1, r = v << 1 | 1;
    build(l, tl, mid);
    build(r, mid + 1, tr);
    maxx[v] = max(maxx[v << 1], maxx[v << 1 | 1]);
    int i = 0, j = 0;
    for(; i < t[l].size(); ++i) {
        while(j < t[r].size() && t[r][j] < t[l][i]) {
            maxx[v] = max(maxx[v], t[l][j] + t[r][j]);
            t[v].pb(t[r][j++]);
        }
        t[v].pb(t[l][i]);
    }
    while(j < t[r].size())
        t[v].pb(t[r][j++]);
}

int get(int v, int tl, int tr, int l, int r) {
    if(tl > r || tr < l)
        return 0;
    if(tl >= l && tr <= r)
        return maxx[v];
    int mid = tl + tr >> 1;
    return max(get(v << 1, tl, mid, l, r), get(v << 1 | 1, mid + 1, tr, l, r));
}

main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    build(1, 1, n);
    while(m--) {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        bool flag = true;
        for(int i = l; i < r; ++i) {
            for(int j = i + 1; j <= r; ++j) {
                if(a[i] > a[j] && a[i] + a[j] > k) {
                    flag = false;
                    break;
                }
            }
        }
        if(!flag)
            puts("0");
        else
            puts("1");
    }
    // for(int i = 1; i <= m; ++i) {
    //     int l, r, k;
        // scanf("%d%d%d", &l, &r, &k);
    //     if(get(1, 1, n, l, r) > k)
    //         puts("0");
    //     else
    //         puts("1");
    // }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'void build(int, int, int)':
sortbooks.cpp:50:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1, l = v << 1, r = v << 1 | 1;
               ~~~^~~~
sortbooks.cpp:55:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(; i < t[l].size(); ++i) {
           ~~^~~~~~~~~~~~~
sortbooks.cpp:56:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(j < t[r].size() && t[r][j] < t[l][i]) {
               ~~^~~~~~~~~~~~~
sortbooks.cpp:62:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(j < t[r].size())
           ~~^~~~~~~~~~~~~
sortbooks.cpp: In function 'int get(int, int, int, int, int)':
sortbooks.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = tl + tr >> 1;
               ~~~^~~~
sortbooks.cpp: At global scope:
sortbooks.cpp:75:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &l, &r, &k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94456 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 92 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 135 ms 94332 KB Output is correct
6 Correct 105 ms 94364 KB Output is correct
7 Correct 113 ms 94504 KB Output is correct
8 Correct 118 ms 94488 KB Output is correct
9 Correct 98 ms 94328 KB Output is correct
10 Correct 116 ms 94328 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94456 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 92 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 135 ms 94332 KB Output is correct
6 Correct 105 ms 94364 KB Output is correct
7 Correct 113 ms 94504 KB Output is correct
8 Correct 118 ms 94488 KB Output is correct
9 Correct 98 ms 94328 KB Output is correct
10 Correct 116 ms 94328 KB Output is correct
11 Correct 877 ms 94564 KB Output is correct
12 Execution timed out 3011 ms 95096 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94456 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 92 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 135 ms 94332 KB Output is correct
6 Correct 105 ms 94364 KB Output is correct
7 Correct 113 ms 94504 KB Output is correct
8 Correct 118 ms 94488 KB Output is correct
9 Correct 98 ms 94328 KB Output is correct
10 Correct 116 ms 94328 KB Output is correct
11 Correct 877 ms 94564 KB Output is correct
12 Execution timed out 3011 ms 95096 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 94456 KB Output is correct
2 Correct 87 ms 94328 KB Output is correct
3 Correct 92 ms 94328 KB Output is correct
4 Correct 87 ms 94328 KB Output is correct
5 Correct 135 ms 94332 KB Output is correct
6 Correct 105 ms 94364 KB Output is correct
7 Correct 113 ms 94504 KB Output is correct
8 Correct 118 ms 94488 KB Output is correct
9 Correct 98 ms 94328 KB Output is correct
10 Correct 116 ms 94328 KB Output is correct
11 Correct 877 ms 94564 KB Output is correct
12 Execution timed out 3011 ms 95096 KB Time limit exceeded
13 Halted 0 ms 0 KB -