Submission #946316

#	Time	Username	Problem	Language	Result	Execution time	Memory
946316		NourWael	Trading (IZhO13_trading)	C++17	100 / 100	161 ms	15700 KiB

trading

#include <bits/extc++.h>
#define int long long 
using namespace std; 
using namespace __gnu_pbds; 
int const mxN = 3e5+5;
int seg[8*mxN], cor[8*mxN];
int n,pw,m,b;

void update ( int node, int l_n, int r_n, int l, int r, int val , int take) {
   if(r_n<=l || l_n>=r) return;
   if(l<=l_n && r>=r_n) { 
      val = (l_n-b) + val;
      seg[node] = max({seg[node],val,take}); 
      return;
   }
   take = max(take, seg[node]);
   int m = (l_n+r_n)/2;
   update(node*2+1, l_n, m, l, r, val, take);
   if(take) take += (m-l_n);
   update(node*2+2, m, r_n, l, r, val, take);
}

void down ( int node, int l, int r, int v) {
   seg[node] = max (seg[node], v);
   if(l==r-1) { cor[l] = node; return; }
   v = max(v,seg[node]);
   int m = (l+r)/2;
   down(node*2+1, l, m, v);
   if(v) v += m-l;
   down(node*2+2, m, r, v);

}

signed main() {
   ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
   
   cin>>n>>m; 
   pw = (1<<(__lg(n)+1)); 
   for(int i=0; i<m; i++) {
      int x,y,c; cin>>x>>y>>c;
      b = x;
      update(0,0,pw,x,y+1, c, 0);
   }
   //for(int i=0; i<=14; i++) cout<<i<<' '<<seg[i]<<'\n';
   down(0,0,pw,0);
   for(int i=1; i<=n; i++) {
     cout<<seg[cor[i]]<<' ';
   }
   return 0;
}

• Subtask 1: 100 / 100