Submission #1015473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015473		vjudge1	Meteors (POI11_met)	C++17	0 / 100	16 ms	65536 KiB

met

#include <bits/stdc++.h>
 
#define FOR(i, a, b)  for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define _ << " _ " <<
#define ll long long
 
using namespace std;
 
const int OFF = (1 << 22);
ll tour[2 * OFF + 10];
 
vector <int> stat[OFF];
int l[OFF], r[OFF];
int beg[OFF], fin[OFF];
ll val[OFF];
ll req[OFF];
vector <int> midovi[OFF];
 
void add(int a, int b, ll va, int lo, int hi, int x) {
    assert(x<=OFF*2+10);
    if (a <= lo && hi <= b) {
        tour[x] += va;
        return;
    }
    if (a >= hi || b <= lo) return;
    int mi = (lo + hi) / 2;
    add(a, b, va, lo, mi, x * 2);
    add(a, b, va, mi, hi, x * 2 + 1);
    return;
}
 
ll sum(int x, ll tr) {
    x += OFF;
    ll out = 0,cnt=0;
    while (x) {
        out += tour[x];
        if (out >= tr) return out;
        x /= 2;
        cnt++;
    }
    return out;
}
int main() {
    ios_base::sync_with_stdio(false);
 
    int n, m;
    cin >> n >> m;
    REP(i, m) {
        int x;
        cin >> x;
        stat[x - 1].push_back(i);
    }
    REP(i, n) cin >> req[i];
 
    int k;
    cin >> k;
    REP(i, k) {
        cin >> l[i] >> r[i] >> val[i];
    }
 
    REP(i, n) {
        beg[i] = 0;
        fin[i] = k + 1;
    }
 
    REP(T, 20) {
        memset(tour, 0, sizeof tour);
        REP(i, k + 2) midovi[i].clear();
 
        REP(i, n) {
            if (beg[i] == fin[i]) continue;
            int mi = (beg[i] + fin[i]) / 2;
            midovi[mi].push_back(i);
        }
 
        REP(i, k + 1) {
            if (i < k) {
                if (l[i] <= r[i])
                    add(l[i] - 1, r[i], val[i], 0, OFF, 1);
                else {
                    add(0,     r[i], val[i], 0, OFF, 1);
                    add(l[i] - 1, m, val[i], 0, OFF, 1);
                }
            }
 
            REP(j, midovi[i].size()) {
                int tr = midovi[i][j];
                ll suma = 0;
                REP(sm, stat[tr].size()) {
                    suma += sum(stat[tr][sm], 1e10);
                }
                if (suma < req[tr]) {
                    beg[tr] = i + 1;
                } else {
                    fin[tr] = i;
                }
            }
        }
    }
 
    REP(i, n) {
        if (beg[i] >= k) {
            cout << "NIE\n";
        } else {
            cout << beg[i] + 1 << endl;
        }
    }
 
    return 0;
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:3:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b)  for (int i = (a); i < (b); i++)
      |                                           ^
met.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define REP(i, n) FOR(i, 0, n)
      |                   ^~~
met.cpp:87:13: note: in expansion of macro 'REP'
   87 |             REP(j, midovi[i].size()) {
      |             ^~~
met.cpp:3:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define FOR(i, a, b)  for (int i = (a); i < (b); i++)
      |                                           ^
met.cpp:4:19: note: in expansion of macro 'FOR'
    4 | #define REP(i, n) FOR(i, 0, n)
      |                   ^~~
met.cpp:90:17: note: in expansion of macro 'REP'
   90 |                 REP(sm, stat[tr].size()) {
      |                 ^~~

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