oj.uz

답안 #392453

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
392453 2021-04-21T07:41:09 Z codebuster_10 Sjeckanje (COCI21_sjeckanje) C++17
110 / 110
 1205 ms 29720 KB 
#include <bits/stdc++.h>

using namespace std ;

#define int int64_t //be careful about this 
#define endl "\n"
#define f(i,a,b) for(int i=int(a);i<int(b);++i)

#define pr pair
#define ar array
#define fr first
#define sc second
#define vt vector
#define pb push_back
#define eb emplace_back
#define LB lower_bound  
#define UB upper_bound
#define PQ priority_queue

#define sz(x) ((int)(x).size())
#define all(a) (a).begin(),(a).end()
#define allr(a) (a).rbegin(),(a).rend()
#define mem0(a) memset(a, 0, sizeof(a))
#define mem1(a) memset(a, -1, sizeof(a))

template<class A> void rd(vt<A>& v);
template<class T> void rd(T& x){ cin >> x; }
template<class H, class... T> void rd(H& h, T&... t) { rd(h) ; rd(t...) ;}
template<class A> void rd(vt<A>& x) { for(auto& a : x) rd(a) ;}

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

template<typename T>
void __p(T a) {
  cout<<a; 
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cout<<"{";
  __p(a.first);
  cout<<",";
  __p(a.second);
  cout<<"}\n"; 
}
template<typename T>
void __p(std::vector<T> a) {
  cout<<"{";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cout<<",}\n"[it+1==a.end()]; 
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cout<<name<<" : ";
  __p(arg1);
  cout<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cout.write(names,comma-names)<<" : ";
  __p(arg1);
  cout<<" | ";
  __f(comma+1,args...);
}

void setIO(string s = "") {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
  cin.exceptions(cin.failbit); 
	cout.precision(15);	cout << fixed;
  #ifdef ONLINE_JUDGE
  if(sz(s)){
  	freopen((s+".in").c_str(),"r",stdin);
  	freopen((s+".out").c_str(),"w",stdout);
  }
  #define __f(...) 0
  #endif
}
const int MAX_N = 6e5 + 7;
int dis[MAX_N];// this stores distances

struct node{
	int dp[2][2]; // 0 means not taken , 1 means taken
};


template<class T> struct SEGTREE { 
  public:  
  	const T ID = {{{0,0},{0,0}}}; 
  	int size ;
    vector<T> seg ;
    T comb(int i, int li, int ri, int j, int lj, int rj){ 
    	assert(ri + 1 == lj);
    	T res = ID;
    	for(int x = 0; x <= 1; x++){
    		for(int y = 0; y <= 1; y++){
    			//calc dp[x][y]
    			for(int u = 0; u <= 1; u++){
    				for(int v = 0; v <= 1; v++){
    					if(u == 1 && v == 1){
    						if((dis[ri] >= 0 && dis[lj] >= 0) || (dis[ri] <= 0 && dis[lj] <= 0)){
    							ckmax(res.dp[x][y], seg[i].dp[x][u] + seg[j].dp[v][y]);
    						}
    					}else{
    						ckmax(res.dp[x][y], seg[i].dp[x][u] + seg[j].dp[v][y]);
    					}
    				}
    			}
    			//__f("i,j",i,j);
    			//__f("x,y,dp[x][y]",x,y,res.dp[x][y]);		
    		}
    	}
    	return res;
    }
    void init(int n){ 
      size = 1 ;
      while(size < n) size *= 2 ;
      seg.assign(2*size, ID); 
    }
    void upd(int p, T val, int x, int lx, int rx) { 
      if( rx - lx == 1 ){
        seg[x] = val ;	return ;
      }
      int mid = (rx + lx)/2 ;
      if(p < mid){
        upd(p, val, 2 * x + 1, lx, mid) ;
      }else{
        upd(p, val, 2 * x + 2, mid, rx) ;
      }
      seg[x] = comb(2 * x + 1, lx, mid - 1, 2 * x + 2, mid, rx - 1);
    }
 
    void upd(int p, T val) { 
      upd(p, val, 0, 0, size) ;
    }
};
signed main(){
  setIO();
  int n,q; rd(n,q);
  vt<int> a(n);
  rd(a);
  f(i,0,n-1) dis[i] = a[i+1] - a[i];
  SEGTREE<node> st;
  st.init(n-1); 
  auto UPD = [&](int i){
  	st.upd(i,{{{0, 0}, {0, abs(dis[i])}}}) ;
  	return;
  };
  auto go = [&](){
  	int res = 0;
  	for(int i = 0; i <= 1; i++){
  		for(int j = 0; j <= 1; j++){
  			ckmax(res,st.seg[0].dp[i][j]);
  		}
  	}
  	return res;
  };
  f(i,0,n-1) UPD(i);
  while(q--){
  	int l,r,x; rd(l,r,x); --l,--r;
  	if(l > 0){
  		dis[l-1] += x;
  		UPD(l-1);
  	}
  	if(r < n-1){
  		dis[r] -= x;
  		UPD(r);
  	} 
  	cout << go() << endl ;
  }
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 11 ms 588 KB Output is correct
8 Correct 11 ms 588 KB Output is correct
9 Correct 11 ms 644 KB Output is correct
10 Correct 10 ms 588 KB Output is correct
11 Correct 11 ms 588 KB Output is correct
12 Correct 10 ms 588 KB Output is correct

Subtask #3
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 11 ms 588 KB Output is correct
8 Correct 11 ms 588 KB Output is correct
9 Correct 11 ms 644 KB Output is correct
10 Correct 10 ms 588 KB Output is correct
11 Correct 11 ms 588 KB Output is correct
12 Correct 10 ms 588 KB Output is correct
13 Correct 1201 ms 26852 KB Output is correct
14 Correct 1205 ms 28936 KB Output is correct
15 Correct 1194 ms 29056 KB Output is correct
16 Correct 1193 ms 28924 KB Output is correct
17 Correct 1142 ms 28872 KB Output is correct
18 Correct 1043 ms 29720 KB Output is correct