#include <iostream>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <string>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <vector>
#include <iterator>
using namespace std;
//defines
#define ll long long
#define usg unsigned
#define kap map
#define print(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cout<<x[for_loop]<<' ';}cout<<endl;
#define read(x, n) for(int for_loop = 0; for_loop < n; for_loop++){cin>>x[for_loop];}
#define speed ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ratdig(x) cout << fixed << setprecision(x);
#define xfixdig(x) cout << setprecision(x);
#define multi int t; cin>>t; presolve(); while(t--) solve()
#define single presolve(); solve(); return 0
#define rev(x) reverse(x.begin(), x.end())
#define all(x) x.begin(), x.end()
//functions
void yn(bool b)
{
if (b)
{
cout << "YES\n";
return;
}
cout << "NO\n";
}
ll gcd(ll a, ll b) {
if (a == 0)
return b;
if (b == 0)
return a;
return gcd(b % a, a);
}
ll lcm(ll a, ll b)
{
return (a * b) / gcd(a, b);
}
string to2(ll a)
{
string r = "";
for (ll i = a; i > 0; )
{
ll k = i % 2;
i /= 2;
char c = k + 48;
r += c;
}
if (a == 0)
{
r = "0";
}
rev(r);
return r;
}
ll binpow(ll a, ll b, ll mod = -1)
{
ll ans = 1;
while (b)
{
if ((b & 1) == 1)
{
ans *= a;
if (mod != -1)
ans %= mod;
}
b >>= 1;
a *= a;
if (mod != -1)
a %= mod;
}
return ans;
}
//body
void presolve()
{
}
#define midd mid + 1
#define poss pos * 2
#define middle ll mid = (l + r) / 2
const int N = 300005;
ll t[4 * N];
void update(int ql, int qr, int l, int r, ll k, int pos)
{
if (ql == l && qr == r)
{
t[pos] = max(k, t[pos]);
return;
}
middle;
if (qr < midd)
{
update(ql, qr, l, mid, k, poss);
return;
}
if (ql > mid)
{
update(ql, qr, midd, r, k, poss + 1);
return;
}
update(ql, mid, l, mid, k, poss);
ll w = k;
if (w > 0)
w += midd - ql;
update(midd, qr, midd, r, w, poss + 1);
}
ll query(int l, int r, int y, ll u, int pos)
{
if (l == r)
{
//cout << y << ' ' << u << ' ' << pos << ' ' << t[pos] << endl;
return max(u, t[pos]);
}
middle;
if (y <= mid)
{
return query(l, mid, y, max(u, t[pos]), poss);
}
else
{
ll w = t[pos];
if (w > 0)
w += midd - l;
ll e = u;
if (e > 0)
e += midd - l;
return query(midd, r, y, max(e, w), poss + 1);
}
}
ll l[N], r[N], x[N];
void solve()
{
ll i, j, k, m, n;
cin >> n >> m;
for (i = 0; i < m; i++)
{
cin >> l[i] >> r[i] >> x[i];
l[i]--;
r[i]--;
update(l[i], r[i], 0, n - 1, x[i], 1);
}
/*for (i = 1; i <= 4 * n; i++)
{
cout << t[i] << ' ';
}
cout << endl;*/
for (i = 0; i < n; i++)
{
cout << query(0, n - 1, i, 0, 1) << ' ';
}
}
int main()
{
speed;
single;
multi;
return 0;
}
Compilation message
trading.cpp: In function 'void solve()':
trading.cpp:157:8: warning: unused variable 'j' [-Wunused-variable]
157 | ll i, j, k, m, n;
| ^
trading.cpp:157:11: warning: unused variable 'k' [-Wunused-variable]
157 | ll i, j, k, m, n;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
2 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
2 ms |
4700 KB |
Output is correct |
| 7 |
Correct |
70 ms |
13012 KB |
Output is correct |
| 8 |
Correct |
79 ms |
14420 KB |
Output is correct |
| 9 |
Correct |
83 ms |
13776 KB |
Output is correct |
| 10 |
Correct |
100 ms |
12652 KB |
Output is correct |
| 11 |
Correct |
92 ms |
15332 KB |
Output is correct |
| 12 |
Correct |
99 ms |
14100 KB |
Output is correct |
| 13 |
Correct |
103 ms |
15044 KB |
Output is correct |
| 14 |
Correct |
104 ms |
14160 KB |
Output is correct |
| 15 |
Correct |
118 ms |
15700 KB |
Output is correct |
| 16 |
Correct |
123 ms |
15700 KB |
Output is correct |
| 17 |
Correct |
123 ms |
17820 KB |
Output is correct |
| 18 |
Correct |
128 ms |
19420 KB |
Output is correct |
| 19 |
Correct |
129 ms |
17748 KB |
Output is correct |
| 20 |
Correct |
149 ms |
20564 KB |
Output is correct |
