Submission #869731

#	Time	Username	Problem	Language	Result	Execution time	Memory
869731		riariti	Meteors (POI11_met)	C++17	74 / 100	2328 ms	51300 KiB

met

#include <bits/stdc++.h>

#ifdef local
#include "../../local.hpp"
#else
%:pragma GCC optimize(3)
%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
%:pragma GCC optimize("-fgcse")
%:pragma GCC optimize("-fgcse-lm")
%:pragma GCC optimize("-fipa-sra")
%:pragma GCC optimize("-ftree-pre")
%:pragma GCC optimize("-ftree-vrp")
%:pragma GCC optimize("-fpeephole2")
%:pragma GCC optimize("-ffast-math")
%:pragma GCC optimize("-fsched-spec")
%:pragma GCC optimize("unroll-loops")
%:pragma GCC optimize("-falign-jumps")
%:pragma GCC optimize("-falign-loops")
%:pragma GCC optimize("-falign-labels")
%:pragma GCC optimize("-fdevirtualize")
%:pragma GCC optimize("-fcaller-saves")
%:pragma GCC optimize("-fcrossjumping")
%:pragma GCC optimize("-fthread-jumps")
%:pragma GCC optimize("-funroll-loops")
%:pragma GCC optimize("-fwhole-program")
%:pragma GCC optimize("-freorder-blocks")
%:pragma GCC optimize("-fschedule-insns")
%:pragma GCC optimize("inline-functions")
%:pragma GCC optimize("-ftree-tail-merge")
%:pragma GCC optimize("-fschedule-insns2")
%:pragma GCC optimize("-fstrict-aliasing")
%:pragma GCC optimize("-fstrict-overflow")
%:pragma GCC optimize("-falign-functions")
%:pragma GCC optimize("-fcse-skip-blocks")
%:pragma GCC optimize("-fcse-follow-jumps")
%:pragma GCC optimize("-fsched-interblock")
%:pragma GCC optimize("-fpartial-inlining")
%:pragma GCC optimize("no-stack-protector")
%:pragma GCC optimize("-freorder-functions")
%:pragma GCC optimize("-findirect-inlining")
%:pragma GCC optimize("-fhoist-adjacent-loads")
%:pragma GCC optimize("-frerun-cse-after-loop")
%:pragma GCC optimize("inline-small-functions")
%:pragma GCC optimize("-finline-small-functions")
%:pragma GCC optimize("-ftree-switch-conversion")
%:pragma GCC optimize("-foptimize-sibling-calls")
%:pragma GCC optimize("-fexpensive-optimizations")
%:pragma GCC optimize("-funsafe-loop-optimizations")
%:pragma GCC optimize("inline-functions-called-once")
%:pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(                                                          \
        "Ofast,no-stack-protector,unroll-loops,omit-frame-pointer,inline")
#pragma GCC target(                                                            \
        "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,popcnt,lzcnt,fma,bmi,bmi2,tune=native")

#define dbg(...)
#endif

using i64 = long long;

// constexpr int MXM = 3E5 + 9;
// constexpr int MXM = 3E3 + 9;

int n, m;

std::vector<int> tree;
void add(int x, i64 val) {
    while (x <= m) {
        tree[x] += val;
        x += (x & -x);
    }
}
i64 sum(int x) {
    i64 s = 0;
    while (x > 0) {
        s += tree[x];
        x -= (x & -x);
    }
    return s;
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

#ifdef local
    freopen("program.in", "r", stdin);
    freopen("program.out", "w", stdout);
    freopen("program.err", "w", stderr);
#endif

    std::cin >> n >> m;
    std::vector<int> o(m + 1);
    for (int i = 1; i <= m; i++) {
        std::cin >> o[i];
    }
    std::vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> p[i];
    }
    int k;
    std::cin >> k;
    std::vector<int> l(k + 1), r(k + 1), a(k + 1);
    for (int i = 1; i <= k; i++) {
        std::cin >> l[i] >> r[i] >> a[i];
    }

    std::map<int, std::vector<int>> ow;
    for (int i = 1; i <= m; i++) {
        ow[o[i]].push_back(i);
    }
    std::vector<int> lo(n + 1, 0 + 1), hi(n + 1, k + 1);

    tree.assign(m + 1, 0);

    bool chk = true;
    std::map<int, std::vector<int>> wrk;
    while (chk) {
        chk = false;

        tree.assign(m + 1, 0);

        for (int i = 1; i <= n; i++) {
            if (lo[i] == hi[i]) {
                continue;
            }

            int m = lo[i] + (hi[i] - lo[i]) / 2;
            wrk[m].push_back(i);
        }

        for (int q = 1; q <= k; q++) {
            if (l[q] <= r[q]) {
                add(l[q], a[q]);
                add(r[q] + 1, -a[q]);
            } else {
                add(1, a[q]);
                add(r[q] + 1, -a[q]);
                add(l[q], a[q]);
            }

            while (!wrk[q].empty()) {
                chk = true;

                auto x = wrk[q].back();
                wrk[q].pop_back();

                i64 su = 0;
                for (auto pls : ow[x]) {
                    su += sum(pls);

                    if (su >= p[x]) {
                        break;
                    }
                }

                if (su >= p[x]) {
                    hi[x] = q;
                } else {
                    lo[x] = q + 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        assert(lo[i] == hi[i]);

        if (lo[i] <= k) {
            std::cout << lo[i] << "\n";
        } else {
            std::cout << "NIE\n";
        }
    }

    return 0;
}

Compilation message (stderr)

met.cpp:26:40: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   26 | %:pragma GCC optimize("-fwhole-program")
      |                                        ^
met.cpp:33:42: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   33 | %:pragma GCC optimize("-fstrict-overflow")
      |                                          ^
met.cpp:35:42: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   35 | %:pragma GCC optimize("-fcse-skip-blocks")
      |                                          ^
met.cpp:49:52: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   49 | %:pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                    ^
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   55 |         "sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,popcnt,lzcnt,fma,bmi,bmi2,tune=native")
      |                                                                                                               ^
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
met.cpp:55:111: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13