oj.uz

Submission #1040307

# Submission time Handle Problem Language Result Execution time Memory
1040307 2024-08-01T00:45:13 Z vjudge1 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 55676 KB 
#include <bits/stdc++.h>
using namespace std;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define fo(i, a, b) for (int i = a; i >= b; i--)
#define minimize(a, b) a = (a < b ? a : b)
#define maximize(a, b) a = (a > b ? a : b) 
#define fi first
#define se second
#define ll long long
#define pii pair <int, int>
#define pb push_back
#define pi acos(-1)
#define sz(a) (int)a.size()
#define getbit(a, b) (((a) >> (b)) & 1)
#define INOUT "main"
#define INFT 0x3f3f3f3f
#define debug(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args)
{
    cout << *it << " = [" << a << "]" << '\n';
    err(++it, args...);
}
#define debug1(a, st, en) { cout << #a << " = ["; int kt = false; f(i, st, en) {if (kt) cout << ", "; kt = true; cout << a[i];} cout << "]\n"; } 

void ctime()
{
    cerr << "\n" << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

void file()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    if (fopen(INOUT".INP", "r")) 
    {
        freopen(INOUT".INP", "r", stdin); 
        freopen(INOUT".OUT", "w", stdout);
    }
}

const int MX_N = 1e6 + 5;
int n, m;
int l, r, mood;
int a[MX_N];
pii t[MX_N * 4];

pii JOIN(pii a, pii b)
{
    if (a.fi > b.fi) return a;
    else return b;
}

void BUILD(int id, int l, int r)
{
    if (l == r)
    {
        t[id] = {a[l], l};
        return;
    }

    int mid = (l + r) / 2;
    BUILD(id * 2, l, mid);
    BUILD(id * 2 + 1, mid + 1, r);

    t[id] = JOIN(t[id * 2], t[id * 2 + 1]);
}

pii GET(int id, int l, int r, int u, int v)
{
    if (r < u || l > v) return {-1, 0};
    if (l >= u && r <= v) return t[id];

    int mid = (l + r) / 2;

    return JOIN(GET(id * 2, l, mid, u, v), GET(id * 2 + 1, mid + 1, r, u, v));
}

bool check(int l, int r)
{
    // debug(l, r);

    if (l >= r) return true;

    bool res = true;
    pii x = GET(1, 1, n, l, r);

    // debug(x.fi);

    if (x.se < r)
    {
        pii x1 = GET(1, 1, n, x.se + 1, r);
        if (x.fi + x1.fi > mood) return false;
    }

    if (!check(l, x.se - 1)) return false;
    return true;
}

int main()
{
    file();

    cin >> n >> m;
    f(i, 1, n) cin >> a[i];
    BUILD(1, 1, n);

    while (m --)
    {
        cin >> l >> r >> mood;

        if (check(l, r)) cout << 1 << '\n';
        else cout << 0 << '\n';
    }

    ctime();
    return 0;
}

Compilation message

sortbooks.cpp: In function 'bool check(int, int)':
sortbooks.cpp:87:10: warning: unused variable 'res' [-Wunused-variable]
   87 |     bool res = true;
      |          ^~~
sortbooks.cpp: In function 'void file()':
sortbooks.cpp:39:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |         freopen(INOUT".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:40:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |         freopen(INOUT".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 5 ms 352 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 1 ms 352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 5 ms 352 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 2 ms 608 KB Output is correct
14 Correct 3 ms 608 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 581 ms 608 KB Output is correct
17 Correct 351 ms 616 KB Output is correct
18 Correct 119 ms 616 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 782 ms 54624 KB Output is correct
2 Correct 797 ms 55676 KB Output is correct
3 Correct 826 ms 55380 KB Output is correct
4 Correct 859 ms 55672 KB Output is correct
5 Execution timed out 3041 ms 30668 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 4948 KB Output is correct
2 Correct 548 ms 5068 KB Output is correct
3 Execution timed out 3036 ms 3416 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 5 ms 352 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 2 ms 608 KB Output is correct
14 Correct 3 ms 608 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 581 ms 608 KB Output is correct
17 Correct 351 ms 616 KB Output is correct
18 Correct 119 ms 616 KB Output is correct
19 Correct 258 ms 12112 KB Output is correct
20 Correct 290 ms 12224 KB Output is correct
21 Correct 272 ms 12116 KB Output is correct
22 Correct 274 ms 12112 KB Output is correct
23 Correct 291 ms 12156 KB Output is correct
24 Execution timed out 3079 ms 7516 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 352 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 5 ms 352 KB Output is correct
9 Correct 2 ms 360 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 2 ms 344 KB Output is correct
12 Correct 2 ms 616 KB Output is correct
13 Correct 2 ms 608 KB Output is correct
14 Correct 3 ms 608 KB Output is correct
15 Correct 3 ms 592 KB Output is correct
16 Correct 581 ms 608 KB Output is correct
17 Correct 351 ms 616 KB Output is correct
18 Correct 119 ms 616 KB Output is correct
19 Correct 782 ms 54624 KB Output is correct
20 Correct 797 ms 55676 KB Output is correct
21 Correct 826 ms 55380 KB Output is correct
22 Correct 859 ms 55672 KB Output is correct
23 Execution timed out 3041 ms 30668 KB Time limit exceeded
24 Halted 0 ms 0 KB -