Submission #162769

#	Time	Username	Problem	Language	Result	Execution time	Memory
162769		abacaba	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	0 / 100	3023 ms	73588 KiB

sortbooks

#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>
#define tm abc

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int mod = 1e9 + 7;
const int inf = 1e9;
const int N = 1e6 + 15;
int n, m, a[N], maxx[N];
bool ans[N];

struct query {
    int l, r, k, ind;
    bool operator < (const query &b) const {
        return l < b.l;
    }
} qs[N];

struct node {
    node *l, *r;
    int key, pr, val, ind, add;
    node(int key, int val, int ind) : key(key), val(val), ind(ind) {
        pr = uniform_int_distribution<>(0, inf)(rng);
        l = r = NULL;
        add = 0;
    }
};

typedef node* pnode;

pnode root = NULL;

inline void tm(int &a, int b) {
    a = max(a, b);
}

inline void push(pnode &t) {
    if(t) {
        if(t->l) {
            tm(t->l->val, t->add);
            tm(t->l->add, t->add);
        }
        if(t->r) {
            tm(t->r->val, t->add);
            tm(t->r->add, t->add);
        }
    }
}

void split(pnode t, pnode &l, pnode &r, int key) {
    if(!t)
        return void(l = r = t);
    push(t);
    if(t->key <= key)
        split(t->r, t->r, r, key), l = t;
    else
        split(t->l, l, t->l, key), r = t;
}

void merge(pnode &t, pnode l, pnode r) {
    push(l);
    push(r);
    if(!l || !r)
        t = l ? l : r;
    else if(l->pr > r->pr)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;
}

inline void insert(pnode &t, pnode nw) {
    pnode t1, t2;
    split(t, t1, t2, nw->key);
    merge(t1, t1, nw);
    merge(t, t1, t2);
}

inline void multiupdate(pnode &t, int l, int r, int val) {
    pnode t1, t2, t3, t4;
    split(t, t1, t2, l - 1);
    split(t2, t3, t4, r);
    if(t3) {
        tm(t3->val, val);
        tm(t3->add, val);
    }
    merge(t2, t3, t4);
    merge(t, t1, t2);
}

void traverse(pnode t) {
    if(t) {
        push(t);
        maxx[t->ind] = t->val;
        traverse(t->l);
        traverse(t->r);
    }
}

set <pii> cur;

main() {
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        cur.insert(mp(a[i], i));
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
        qs[i].ind = i;
    }
    sort(qs + 1, qs + 1 + m);
    for(int i = 1, j = 1; i <= n; ++i) {
        while(j <= m && qs[j].l <= i) {
            insert(root, new node(qs[j].r, 0, j));
            ++j;
        }
        set <pii>::iterator it = cur.lower_bound(mp(a[i], -inf));
        pii val = mp(0, 0);
        if(it != cur.begin()) {
            --it;
            val = mp(a[i] + it->f, it->se);
        }
        if(val.f)
            multiupdate(root, val.se, n, val.f);
        cur.erase(mp(a[i], i));
    }
    traverse(root);
    for(int i = 1; i <= m; ++i) {
        if(maxx[i] <= qs[i].k)
            ans[qs[i].ind] = true;
    }
    for(int i = 1; i <= m; ++i)
        puts(ans[i] ? "1" : "0");
    return 0;
}

Compilation message (stderr)

sortbooks.cpp:137:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
sortbooks.cpp: In function 'int main()':
sortbooks.cpp:138: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:140:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
sortbooks.cpp:144:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &qs[i].l, &qs[i].r, &qs[i].k);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23