oj.uz

Submission #160745

# Submission time Handle Problem Language Result Execution time Memory
160745 2019-10-29T18:01:17 Z shashwatchandra Trading (IZhO13_trading) C++17
100 / 100
 395 ms 17528 KB 
/*input
6 4
4 4 3
1 2 5
5 6 1
6 6 1
*/
#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;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 3e5+1;
int n,q;
int lazy[4*N];

#define child 2*node
#define mid (l+r)/2

void pushdown(int node,int l,int r){
	if(l == r)return;
	lazy[child] = max(lazy[child],lazy[node]);
	lazy[child+1] = max(lazy[child+1],lazy[node]);
}

void upd(int node,int l,int r,int start,int end,int val){
	pushdown(node,l,r);
	if(l > end or start > r)return;
	if(start <= l and r <= end){
		lazy[node] = max(lazy[node],val);
		pushdown(node,l,r);
		return;
	}
	upd(child,l,mid,start,end,val);
	upd(child+1,mid+1,r,start,end,val);
}

int getval(int node,int l,int r,int ind){
	pushdown(node,l,r);
	if(l == r)return lazy[node];
	if(ind <= mid)return getval(child,l,mid,ind);
	return getval(child+1,mid+1,r,ind);
}

void solve(){
  	cin >> n >> q;
  	RE(i,4*n)lazy[i] = -INF;
  	RE(i,q){
  		int l,r,x;cin >> l >> r >> x;
  		upd(1,1,n,l,r,x-l);
  	}
  	RE(i,n){
  		int ans = getval(1,1,n,i)+i;
  		if(ans < 0)ans = 0;
  		cout << ans << " ";
  	}
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 4 ms 504 KB Output is correct
7 Correct 157 ms 8840 KB Output is correct
8 Correct 172 ms 9848 KB Output is correct
9 Correct 176 ms 10104 KB Output is correct
10 Correct 199 ms 10860 KB Output is correct
11 Correct 207 ms 11896 KB Output is correct
12 Correct 219 ms 12392 KB Output is correct
13 Correct 235 ms 13064 KB Output is correct
14 Correct 235 ms 13176 KB Output is correct
15 Correct 266 ms 14456 KB Output is correct
16 Correct 308 ms 14584 KB Output is correct
17 Correct 262 ms 15064 KB Output is correct
18 Correct 296 ms 15664 KB Output is correct
19 Correct 281 ms 15736 KB Output is correct
20 Correct 395 ms 17528 KB Output is correct