제출 #142937

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
142937		model_code	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3014 ms	102608 KiB

sortbooks

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 17 / 17
• Subtask 5: 30 / 30
• Subtask 6: 0 / 23