oj.uz

Submission #602232

# Submission time Handle Problem Language Result Execution time Memory
602232 2022-07-22T18:10:17 Z Ozy Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 872 ms 92068 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000
#define val first
#define id second

//puede ser que arruine la memoria
//checar
set<int> st[MAX*4];
int n,q,offset,izq,der,l,r,k,ini,fin,mitad,a;
set<int>::iterator x,y;
pair<lli,lli> mayores[MAX*4],act;
bool res;

pair<lli,lli> busca(lli pos, lli ini, lli fin ,lli l, lli r) {

    if (ini > r || fin < l) return {0,0};
    if (l <= ini && fin <= r) return mayores[pos];

    lli mitad=(ini+fin)/2;
    pair<int,int> a = busca(pos*2, ini,mitad,l,r);
    pair<int,int> b = busca((pos*2)+1, mitad+1,fin,l,r);

    return (a.val > b.val)? a : b;

}

int query(lli pos, lli ini, lli fin, lli l, lli r, lli lim) {

    if (l > r) return -1;
    if (ini > r || fin < l) return -1;
    if (l <= ini && fin <= r) {
        x = st[pos].lower_bound(lim);
        if (x == st[pos].begin()) return -1;
        x--;
        return (*x);
    }

    lli mitad = (ini+fin)/2;
    lli a = query(pos*2,ini,mitad,l,r,lim);
    lli b = query((pos*2)+1,mitad+1,fin,l,r,lim);
    return max(a,b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    offset = 1;
    while (offset < n) offset<<=1;

    rep(i,0,n-1) {
        cin >> a;
        st[offset+i].emplace_hint(st[i+offset].end(), a);
        mayores[offset+i] = {a,i+1};
    }
    repa(i,offset-1,1) {

        //mezclar
        izq = i*2;
        x = st[izq].begin();

        der = (i*2)+1;
        y = st[der].begin();

        while (y != st[der].end() || x != st[izq].end()) {

            if (y == st[der].end()) {
                st[i].emplace_hint(st[i].end(), *x);
                x++;
                continue;
            }
            if (x == st[izq].end()) {
                st[i].emplace_hint(st[i].end(), (*y));
                y++;
                continue;
            }

            if ((*x) == (*y)) {
                st[i].emplace_hint(st[i].end(), *y);
                y++;
                x++;
                continue;
            }

            if ((*x) < (*y)) {
                st[i].emplace_hint(st[i].end(), *x);
                x++;
                continue;
            }
            else {
                st[i].emplace_hint(st[i].end(), *y);
                y++;
                continue;
            }
        }

        if (mayores[izq].val >= mayores[der].val) mayores[i] = mayores[izq];
        else mayores[i] = mayores[der];
    }

    rep(Q,1,q) {

        cin >> l >> r >> k;
        res =true;
        ini = l;
        fin = r;
        while (ini <= fin) {
            mitad = (ini+fin)/2;
            act = busca(1,1,offset,l,mitad);

            a = query(1,1,offset,act.id+1,r,act.val);

            if (a == -1) {
                fin = mitad - 1;
                continue;
            }
            ini = mitad + 1;

            if (act.val + a > k) {
                res = false;
                break;
            }
        }

        if (res) cout << 1 << "\n";
        else cout << "0\n";
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 22 ms 37880 KB Output is correct
3 Correct 19 ms 37908 KB Output is correct
4 Incorrect 19 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 22 ms 37880 KB Output is correct
3 Correct 19 ms 37908 KB Output is correct
4 Incorrect 19 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 76544 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 22 ms 37880 KB Output is correct
3 Correct 19 ms 37908 KB Output is correct
4 Incorrect 19 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37844 KB Output is correct
2 Correct 22 ms 37880 KB Output is correct
3 Correct 19 ms 37908 KB Output is correct
4 Incorrect 19 ms 37844 KB Output isn't correct
5 Halted 0 ms 0 KB -