| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 762425 |
2023-06-21T11:47:43 Z |
Chal1shkan |
Meteors (POI11_met) |
C++14 |
|
5394 ms |
65536 KB |
//Bismillahir-Rahmanir-Rahim
# include <bits/stdc++.h>
# define pb push_back
# define ff first
# define ss second
# define nl "\n"
# define sz(x) ((int)(x).size())
# define deb(x) cerr << #x << " = " << x << endl;
# define pll pair <ll, ll>
# define pii pair <int, int>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll maxn = 3e5 + 25;
const ll inf = 2e18 + 0;
const ll mod = 1e9 + 7;
const ll dx[] = {-1, 1, 0, 0};
const ll dy[] = {0, 0, -1, 1};
const ll P = 67;
using namespace std;
ll n, m, q, tl[maxn], tr[maxn];
vector <ll> boss[maxn];
ll need[maxn], ans[maxn];
ll l[maxn], r[maxn], a[maxn];
vector <ll> check[maxn];
struct segtree
{
ll t[maxn * 4];
ll z[maxn * 4];
void build (ll v = 1, ll tl = 1, ll tr = m)
{
t[v] = z[v] = 0;
if (tl == tr)
{
return;
}
ll tm = (tl + tr) >> 1;
build (v * 2, tl, tm);
build (v * 2 + 1, tm + 1, tr);
}
void push (ll v, ll tl, ll tr)
{
if (z[v] && tl != tr)
{
ll tm = (tl + tr) >> 1;
t[v * 2] += z[v] * 1LL * (tm - tl + 1);
t[v * 2 + 1] += z[v] * 1LL * (tr - tm);
z[v * 2] += z[v];
z[v * 2 + 1] += z[v];
z[v] = 0;
}
}
void update (ll l, ll r, ll x, ll v = 1, ll tl = 1, ll tr = m)
{
push(v, tl, tr);
if (tr < l || r < tl) return;
if (l <= tl && tr <= r)
{
t[v] += x * 1LL * (tr - tl + 1);
z[v] += x;
return;
}
ll tm = (tl + tr) >> 1;
update(l, r, x, v * 2, tl, tm);
update(l, r, x, v * 2 + 1, tm + 1, tr);
t[v] = t[v * 2] + t[v * 2 + 1];
}
ll get (ll pos, ll v = 1, ll tl = 1, ll tr = m)
{
push(v, tl, tr);
if (tl == tr)
{
return t[v];
}
ll tm = (tl + tr) >> 1;
if (pos <= tm)
return get(pos, v * 2, tl, tm);
else
return get(pos, v * 2 + 1, tm + 1, tr);
}
} t;
void ma1n (/* SABR */)
{
cin >> n >> m;
for (ll i = 1; i <= m; ++i)
{
ll owner;
cin >> owner;
boss[owner].pb(i);
}
for (ll i = 1; i <= n; ++i)
{
cin >> need[i];
}
cin >> q;
for (ll i = 1; i <= q; ++i)
{
cin >> l[i] >> r[i] >> a[i];
}
for (ll i = 1; i <= n; ++i)
{
tl[i] = 1, tr[i] = q, ans[i] = -1;
}
bool boo = 1;
while (boo)
{
boo = 0;
t.build();
for (ll i = 1; i <= n; ++i)
{
if (tl[i] <= tr[i])
{
check[(tl[i] + tr[i]) >> 1].pb(i);
}
// cout << tl[i] << ' ' << tr[i] << nl;
}
for (ll i = 1; i <= q; ++i)
{
if (l[i] <= r[i])
{
t.update(l[i], r[i], a[i]);
}
else
{
t.update(l[i], m, a[i]);
t.update(1, r[i], a[i]);
}
while (!check[i].empty())
{
boo = 1;
ll id = check[i].back();
check[i].pop_back();
ll sum = 0;
for (ll x : boss[id])
{
sum += t.get(x);
if (sum >= need[id]) break;
}
if (sum >= need[id])
{
tr[id] = i - 1;
ans[id] = i;
}
else
{
tl[id] = i + 1;
}
}
}
}
for (ll i = 1; i <= n; ++i)
{
if (ans[i] == -1)
{
cout << "NIE" << nl;
}
else
{
cout << ans[i] << nl;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("file.in", "r", stdin);
// freopen("file.out", "w", stdout);
int ttt = 1;
// cin >> ttt;
for (int test = 1; test <= ttt; ++test)
{
// cout << "Case " << test << ":" << '\n';
ma1n();
}
return 0;
}
// 998batrr | BbIWEJI 3A TObOU!!!
// tourist | BbIWEJI 3A TObOU!!!
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14548 KB |
Output is correct |
| 2 |
Correct |
13 ms |
14596 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
14620 KB |
Output is correct |
| 2 |
Correct |
10 ms |
14548 KB |
Output is correct |
| 3 |
Correct |
12 ms |
14700 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
416 ms |
19724 KB |
Output is correct |
| 2 |
Correct |
524 ms |
23196 KB |
Output is correct |
| 3 |
Correct |
519 ms |
21940 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
511 ms |
21128 KB |
Output is correct |
| 2 |
Correct |
514 ms |
21152 KB |
Output is correct |
| 3 |
Correct |
527 ms |
23456 KB |
Output is correct |
| 4 |
Correct |
96 ms |
20228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
20100 KB |
Output is correct |
| 2 |
Correct |
332 ms |
23732 KB |
Output is correct |
| 3 |
Correct |
230 ms |
16248 KB |
Output is correct |
| 4 |
Correct |
490 ms |
22592 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
477 ms |
18800 KB |
Output is correct |
| 2 |
Correct |
478 ms |
21092 KB |
Output is correct |
| 3 |
Correct |
447 ms |
19200 KB |
Output is correct |
| 4 |
Correct |
513 ms |
24928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5394 ms |
63776 KB |
Output is correct |
| 2 |
Correct |
2140 ms |
41616 KB |
Output is correct |
| 3 |
Correct |
1242 ms |
22816 KB |
Output is correct |
| 4 |
Runtime error |
2103 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5049 ms |
62048 KB |
Output is correct |
| 2 |
Correct |
1234 ms |
41680 KB |
Output is correct |
| 3 |
Correct |
1000 ms |
22076 KB |
Output is correct |
| 4 |
Runtime error |
1625 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Halted |
0 ms |
0 KB |
- |
