Submission #875402

#	Time	Username	Problem	Language	Result	Execution time	Memory
875402		auslander	Trading (IZhO13_trading)	C++17	100 / 100	149 ms	20564 KiB

trading

#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 (stderr)

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;
      |           ^

• Subtask 1: 100 / 100