제출 #869749

#제출 시각아이디문제언어결과실행 시간메모리
869749riariti새로운 문제 (POI11_met)C++17
100 / 100
4929 ms65536 KiB
#include <bits/stdc++.h> #define ll long long #define pb push_back #define all(x) x.begin(), x.end() #define F first #define S second using namespace std; const ll N = 3e5 + 5; const ll NN = 2e6 + 5; const ll INF = -1e1; const ll MOD = 1e9 + 7; const ll LG = 18; int z[N], x[N]; ll t[4 * N], b[N], c[N]; pair<int, int> seq[N]; set<int> MID[N]; vector<int> rg[N]; void build(int v, int l, int r) { t[v] = 0; if (l == r) { t[v] = 0; return; } int mid = (l + r) / 2; build(v + v, l, mid); build(v + v + 1, mid + 1, r); } void upd(int v, int l, int r, int ql, int qr, ll x) { if (ql <= l && r <= qr) { t[v] += x; return; } if (ql > r || qr < l) return; int mid = (l + r) / 2; upd(v + v, l, mid, ql, qr, x); upd(v + v + 1, mid + 1, r, ql, qr, x); } ll get(int v, int l, int r, int pos, ll sum) { sum += t[v]; if (l == r) return sum; int mid = (l + r) / 2; if (pos <= mid) return get(v + v, l, mid, pos, sum); else return get(v + v + 1, mid + 1, r, pos, sum); } void solve() { int n, m; cin >> n >> m; for (int i = 1; i <= m; i++) { int u; cin >> u; rg[u].pb(i); } for (int i = 1; i <= n; i++) { cin >> b[i]; } int q; cin >> q; for (int i = 1; i <= q; i++) { cin >> z[i] >> x[i] >> c[i]; } for (int i = 1; i <= n; i++) { seq[i] = {1, q}; } int tt = 19; while (tt--) { for (int i = 1; i <= n; i++) { int md = (seq[i].F + seq[i].S) / 2; MID[md].insert(i); } build(1, 1, m); for (int i = 1; i <= q; i++) { if (z[i] > x[i]) { upd(1, 1, m, 1, x[i], c[i]); upd(1, 1, m, z[i], m, c[i]); } else { upd(1, 1, m, z[i], x[i], c[i]); } for (int to : MID[i]) { ll sum = 0; for (int d : rg[to]) { sum += get(1, 1, m, d, 0); if (sum >= b[to]) break; } if (sum >= b[to]) { seq[to].S = i; } else { seq[to].F = i + 1; } } } for (int i = 1; i <= q; i++) { MID[i].clear(); } } for (int i = 1; i <= n; i++) { if (seq[i].F <= q) { cout << seq[i].F << '\n'; } else { cout << "NIE\n"; } } } main() { ios_base::sync_with_stdio(0); cin.tie(0); // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); ll abd = 1; // cin >> abd; for (ll i = 1; i <= abd; i++) { // cout << "Case " << i << ":\n"; solve(); } }

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

met.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 | main() {
      | ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...