| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 890481 |
2023-12-21T10:05:47 Z |
vjudge1 |
Meteors (POI11_met) |
C++17 |
|
2332 ms |
52564 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
//#pragma GCC optimization("g", on)
//#pragma GCC optimization("03")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("inline")
//#pragma GCC optimize("-fgcse,-fgcse-lm")
//#pragma GCC optimize("-ftree-pre,-ftree-vrp")
//#pragma GCC optimize("-ffast-math")
//#pragma GCC optimize("-fipa-sra")
//#pragma GCC optimize("-fpeephole2")
//#pragma GCC optimize("-fsched-spec")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("unroll-loops")
#define aboba ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define br break;
#define sp " "
#define en "\n"
#define pb push_back
#define sz(a) int(a.size())
#define bg begin()
#define ed end()
#define in insert
#define ss second
#define ff first
#define setp(a) cout << fixed; cout << setprecision(a)
#define all(v) v.begin(), v.end()
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef double db;
typedef tree<
long long,
null_type,
less_equal<long long>,
rb_tree_tag,
tree_order_statistics_node_update> orset;
void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
ll bm(ll x, ll y, ll z) { ll res = 0; while (y) { if (y & 1) (res += x) %= z; (x += x) %= z; y >>= 1; } return res; }
ll bp(ll x, ll y, ll z) { ll res = 1; x %= z; while (y) { if (y & 1) { (res *= x) %= z; y--; } (x *= x) %= z; y >>= 1; } return res; }
// C(n, k) = ((fact[n] * bp(fact[k], mod - 2)) % mod * bp(fact[n - k], mod - 2)) % mod;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; }
const ll N = 3e5 + 11;
const ll inf = 1e18 + 7;
ll tt = 1;
ll n, m, a[N], b[N];
ll ans[N], sum[N], d[N];
vector<ll> g[N], gr[N];
ll l[N], r[N], x[N];
bool ok[N];
void solve() {
cin >> n >> m;
for (int i = 1;i <= m;i++) {
cin >> a[i];
g[a[i]].pb(i);
}
for (int i = 1;i <= n;i++) cin >> b[i], ans[i] = -1;
ll k; cin >> k;
ll B = min(k, 600ll);
for (ll i = 1;i <= k;i++) {
cin >> l[i] >> r[i] >> x[i];
if (l[i] > r[i]) {
d[1] += x[i];
d[r[i] + 1] -= x[i];
d[l[i]] += x[i];
d[m + 1] -= x[i];
} else {
d[l[i]] += x[i];
d[r[i] + 1] -= x[i];
}
if (i % B == 0 || i == k) {
ll tm = 0;
for (int j = 1;j <= n;j++) sum[j] = 0;
for (int j = 1;j <= m;j++) {
tm += d[j];
sum[a[j]] += tm;
}
for (int j = 1;j <= n;j++) {
// cout << sum[j] << sp << j << sp << i << en;
if (sum[j] >= b[j] && ans[j] == -1) {
ans[j] = (i - 1) / B;
// cout << j << en;
gr[(i - 1) / B].pb(j);
}
}
}
}
for (int i = 1;i <= m;i++) d[i] = 0;
for (int i = 1;i <= n;i++) sum[i] = 0;
for (ll i = 1;i <= k;i++) {
for (auto to : gr[(i - 1) / B]) {
if (ok[to]) continue;
if (g[to].empty()) continue;
if (l[i] > r[i]) {
ll pos = lower_bound(all(g[to]), l[i]) - g[to].bg;
// cout << pos << sp << i << sp << to << en;
sum[to] += x[i] * (sz(g[to]) - pos);
pos = upper_bound(all(g[to]), r[i]) - g[to].bg;
sum[to] += x[i] * pos;
} else {
ll pos = lower_bound(all(g[to]), l[i]) - g[to].bg;
ll pos1 = upper_bound(all(g[to]), r[i]) - g[to].bg;
pos1--;
if (pos1 < 0 || pos == sz(g[to])) continue;
sum[to] += x[i] * (pos1 - pos + 1);
}
if (sum[to] >= b[to]) {
ok[to] = 1;
ans[to] = i;
}
}
if (l[i] > r[i]) {
d[1] += x[i];
d[r[i] + 1] -= x[i];
d[l[i]] += x[i];
d[m + 1] -= x[i];
} else {
d[l[i]] += x[i];
d[r[i] + 1] -= x[i];
}
if (i % B == 0 || i == k) {
ll tm = 0;
for (int j = 1;j <= n;j++) sum[j] = 0;
for (int j = 1;j <= m;j++) {
tm += d[j];
sum[a[j]] += tm;
}
}
}
for (int i = 1;i <= n;i++) {
if (ans[i] == -1) cout << "NIE" << en;
else cout << ans[i] << en;
}
}
int main() {
aboba
// freopen("haircut");
// precalc();
// cin >> tt;
for (int i = 1;i <= tt;i++) {
solve();
}
}
Compilation message
met.cpp: In function 'void freopen(std::string)':
met.cpp:47:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:47:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
31064 KB |
Output is correct |
| 2 |
Correct |
5 ms |
31068 KB |
Output is correct |
| 3 |
Correct |
7 ms |
31272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
31068 KB |
Output is correct |
| 2 |
Correct |
6 ms |
31068 KB |
Output is correct |
| 3 |
Correct |
7 ms |
31252 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
33880 KB |
Output is correct |
| 2 |
Correct |
33 ms |
35304 KB |
Output is correct |
| 3 |
Correct |
136 ms |
35380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
34236 KB |
Output is correct |
| 2 |
Correct |
74 ms |
35160 KB |
Output is correct |
| 3 |
Correct |
94 ms |
35792 KB |
Output is correct |
| 4 |
Correct |
34 ms |
34644 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
33884 KB |
Output is correct |
| 2 |
Correct |
64 ms |
34168 KB |
Output is correct |
| 3 |
Correct |
15 ms |
31580 KB |
Output is correct |
| 4 |
Correct |
86 ms |
35384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
33752 KB |
Output is correct |
| 2 |
Correct |
69 ms |
33940 KB |
Output is correct |
| 3 |
Correct |
36 ms |
34900 KB |
Output is correct |
| 4 |
Correct |
106 ms |
35664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2098 ms |
40224 KB |
Output is correct |
| 2 |
Correct |
729 ms |
43748 KB |
Output is correct |
| 3 |
Correct |
43 ms |
33360 KB |
Output is correct |
| 4 |
Correct |
2332 ms |
51568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1420 ms |
39936 KB |
Output is correct |
| 2 |
Correct |
720 ms |
42280 KB |
Output is correct |
| 3 |
Correct |
42 ms |
34444 KB |
Output is correct |
| 4 |
Correct |
1752 ms |
52564 KB |
Output is correct |
