oj.uz

Submission #142937

# Submission time Handle Problem Language Result Execution time Memory
142937 2019-08-12T08:32:28 Z model_code Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
64 / 100
 3000 ms 102608 KB 
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <algorithm>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <cassert>
#include <unordered_map>
#include <bitset>
#include <unordered_set>

using namespace std;

#define pb push_back
#define pp pop_back
#define f first
#define s second
#define mp make_pair
#define sz(a) (int)((a).size())
#ifdef _WIN32
#  define I64 "%I64d"
#else
#  define I64 "%lld"
#endif
#define fname "."

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair < int, int > pi;
typedef pair < int, ull > pu;
typedef pair < ll, ll > pl;

const int inf = (int)1e9 + 123;
const int MAX_N = (int)1e6 + 123;
const int mod = (int)1e9 + 7;

int n;
int a[MAX_N];

// --------- segment tree for minimum

pi t[4 * MAX_N];

void build(int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
        t[v] = mp(a[tl], tl);
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

void update(int x, int y, int v = 1, int tl = 1, int tr = n) {
    if (tl == tr) {
        t[v] = mp(y, tl);
        return;
    }
    int tm = (tl + tr) / 2;
    if (x <= tm)
        update(x, y, v * 2, tl, tm);
    else
        update(x, y, v * 2 + 1, tm + 1, tr);
    t[v] = min(t[v * 2], t[v * 2 + 1]);
}

pi get(int l, int r, int v = 1, int tl = 1, int tr = n) {
    if (l > r || tl > r || l > tr)
        return mp(inf, -1);
    if (tl >= l && tr <= r)
        return t[v];
    int tm = (tl + tr) / 2;
    return min(get(l, r, v * 2, tl, tm), get(l, r, v * 2 + 1, tm + 1, tr));
}

// --------- maximum of sum of pairs

struct node {
    int maxiSum, maxiF, maxiS, pushVal;
    node operator + (const node &b) {
        node res = node({-inf - inf, -inf, -inf, -1});
        res.maxiF = max(maxiF, b.maxiF);
        res.maxiS = max(maxiS, b.maxiS);
        res.maxiSum = max(maxiSum, b.maxiSum);
        return res;
    }
} mx[4 * MAX_N];

void buildMax(int v = 1, int tl = 1, int tr = n) {
    mx[v] = node({-inf - inf, -inf, -inf, -1});
    if (tl == tr) {
        return;
    }
    int tm = (tl + tr) / 2;
    buildMax(v * 2, tl, tm);
    buildMax(v * 2 + 1, tm + 1, tr);
}

void push(int v, int tl, int tr) {
    if (mx[v].pushVal == -1)
        return;
    mx[v].maxiF = mx[v].pushVal;
    mx[v].maxiSum = mx[v].maxiS + mx[v].pushVal;
    if (tl != tr) {
        mx[v * 2].pushVal = mx[v * 2 + 1].pushVal = mx[v].pushVal;
    }
    mx[v].pushVal = -1;
}

void updateMax(int l, int r, int newVal, bool tp, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > r || tl > r || l > tr)
        return;
    if (tl >= l && tr <= r) {
        if (!tp) {
            mx[v].pushVal = newVal;
            push(v, tl, tr);
        } else {
            assert(tl == tr);
            mx[v].maxiS = newVal;
            mx[v].maxiSum = mx[v].maxiF + mx[v].maxiS;
        }
        return;
    }
    int tm = (tl + tr) / 2;
    updateMax(l, r, newVal, tp, v * 2, tl, tm);
    updateMax(l, r, newVal, tp, v * 2 + 1, tm + 1, tr);
    mx[v] = mx[v * 2] + mx[v * 2 + 1];
}

node getMax(int l, int r, int v = 1, int tl = 1, int tr = n) {
    push(v, tl, tr);
    if (l > r || tl > r || l > tr)
        return node({-inf - inf, -inf, -inf, -1});
    if (tl >= l && tr <= r)
        return mx[v];
    int tm = (tl + tr) / 2;
    return getMax(l, r, v * 2, tl, tm) + getMax(l, r, v * 2 + 1, tm + 1, tr);
}

// ------------

int q;
vector < pair < int, pi > > query[MAX_N];
int ans[MAX_N];

vector < pi > st;

int main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = 1, l, r, x; i <= q; i++) {
        scanf("%d%d%d", &l, &r, &x);
        ans[i] = -1;
        if (l == r) {
            ans[i] = 1;
        } else {
            query[l].pb(mp(i, mp(r, x)));
        }
    }
    buildMax();
    build();
    for (int i = n - 1; i > 0; i--) {
        while(1) {
            pi now = get(i + 1, n);
            if (now.f >= a[i])
                break;
            update(now.s, inf);
//            cout << "on at " << i << " is " << now.s << endl;
            updateMax(now.s, now.s, a[now.s], 1);
        }
        while(!st.empty() && a[i] >= st.back().f) {
            st.pp();
        }
        int l = i + 1, r = (st.empty() ? n : st.back().s);
        updateMax(l, r, a[i], 0);
//        cout << "update max " << l << ' ' << r << " with " << a[i] << endl;
        
        st.pb(mp(a[i], i));
        for (auto j : query[i]) {
            node cur = getMax(i + 1, j.s.f);
//            cout << i + 1 << " bw " << j.s.f << " is " << cur.maxiSum <<  ' '  << cur.maxiF << ' ' << cur.maxiS << endl;
            ans[j.f] = (cur.maxiSum <= j.s.s);
        }
    }
    
    for (int i = 1; i <= q; i++) {
        assert(ans[i] != -1);
        printf("%d\n", ans[i]);
    }
    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:165:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &l, &r, &x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23932 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 23 ms 23872 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23932 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 23 ms 23872 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 26 ms 23928 KB Output is correct
12 Correct 32 ms 24312 KB Output is correct
13 Correct 32 ms 24312 KB Output is correct
14 Correct 34 ms 24316 KB Output is correct
15 Correct 34 ms 24312 KB Output is correct
16 Correct 31 ms 24440 KB Output is correct
17 Correct 29 ms 24156 KB Output is correct
18 Correct 32 ms 24312 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 33276 KB Output is correct
2 Correct 336 ms 33144 KB Output is correct
3 Correct 235 ms 33112 KB Output is correct
4 Correct 239 ms 33148 KB Output is correct
5 Correct 240 ms 33272 KB Output is correct
6 Correct 196 ms 32724 KB Output is correct
7 Correct 198 ms 32760 KB Output is correct
8 Correct 269 ms 32816 KB Output is correct
9 Correct 82 ms 26028 KB Output is correct
10 Correct 260 ms 32784 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23932 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 23 ms 23872 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 26 ms 23928 KB Output is correct
12 Correct 32 ms 24312 KB Output is correct
13 Correct 32 ms 24312 KB Output is correct
14 Correct 34 ms 24316 KB Output is correct
15 Correct 34 ms 24312 KB Output is correct
16 Correct 31 ms 24440 KB Output is correct
17 Correct 29 ms 24156 KB Output is correct
18 Correct 32 ms 24312 KB Output is correct
19 Correct 704 ms 42588 KB Output is correct
20 Correct 699 ms 42580 KB Output is correct
21 Correct 600 ms 42076 KB Output is correct
22 Correct 604 ms 42352 KB Output is correct
23 Correct 603 ms 42232 KB Output is correct
24 Correct 417 ms 43888 KB Output is correct
25 Correct 422 ms 44136 KB Output is correct
26 Correct 459 ms 44060 KB Output is correct
27 Correct 457 ms 44068 KB Output is correct
28 Correct 477 ms 44068 KB Output is correct
29 Correct 503 ms 44392 KB Output is correct
30 Correct 512 ms 44436 KB Output is correct
31 Correct 501 ms 44340 KB Output is correct
32 Correct 500 ms 44456 KB Output is correct
33 Correct 503 ms 44396 KB Output is correct
34 Correct 387 ms 43256 KB Output is correct
35 Correct 394 ms 43412 KB Output is correct
36 Correct 387 ms 43248 KB Output is correct
37 Correct 388 ms 43404 KB Output is correct
38 Correct 385 ms 43124 KB Output is correct
39 Correct 511 ms 44048 KB Output is correct
40 Correct 351 ms 36844 KB Output is correct
41 Correct 571 ms 41896 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23800 KB Output is correct
2 Correct 22 ms 23800 KB Output is correct
3 Correct 23 ms 23932 KB Output is correct
4 Correct 22 ms 23800 KB Output is correct
5 Correct 23 ms 23928 KB Output is correct
6 Correct 23 ms 23800 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 23 ms 23872 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 22 ms 23800 KB Output is correct
11 Correct 26 ms 23928 KB Output is correct
12 Correct 32 ms 24312 KB Output is correct
13 Correct 32 ms 24312 KB Output is correct
14 Correct 34 ms 24316 KB Output is correct
15 Correct 34 ms 24312 KB Output is correct
16 Correct 31 ms 24440 KB Output is correct
17 Correct 29 ms 24156 KB Output is correct
18 Correct 32 ms 24312 KB Output is correct
19 Execution timed out 3014 ms 102608 KB Time limit exceeded
20 Halted 0 ms 0 KB -