제출 #346064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
346064		CSQ31	Wall (IOI14_wall)	C++14	0 / 100	943 ms	34668 KiB

wall

#include "wall.h"
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+7)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
struct node{
	ll mn=0,mx=0;
	ll lmn=INF,lmx=-INF;
};
const int MAXN = 2e6;
vector<node>t;
void mxx(node &a,node &b){
	b.mx = max(b.mx,a.lmx);
	b.mn = max(b.mn,a.lmx);
	b.lmx = max(b.lmx,a.lmx);
	a.lmx = -INF;
	b.lmn = INF;
}
void mnn(node &a,node &b){
	b.mx = min(b.mx,a.lmn);
	b.mn = min(b.mn,a.lmn);
	b.lmn = min(b.lmn,a.lmn);
	a.lmn = INF;
	b.lmx = -INF;	
}
void pushdown(int v){
	if(t[v].lmx != -INF){
		ll tmp = t[v].lmx;
		mxx(t[v],t[2*v]);
		t[v].lmx = tmp;
		mxx(t[v],t[2*v+1]);
	}else if(t[v].lmn != INF){
		ll tmp = t[v].lmn;
		mnn(t[v],t[2*v]);
		t[v].lmn = tmp;
		mnn(t[v],t[2*v+1]);
	}
}
vector<ll>ans;
void upd(int v,int l,int r,int tl,int tr,int mode,ll val){
	if(l > r)return;
	pushdown(v);
	if(l == tl && r == tr){
		if(mode){
			t[v].mx = max(t[v].mx,val);
			t[v].mn = max(t[v].mn,val);
			t[v].lmx = max(t[v].lmx,val);
			t[v].lmn = INF;
		}else{
			t[v].mx = min(t[v].mx,val);
			t[v].mn = min(t[v].mn,val);
			t[v].lmn = min(t[v].lmn,val);
			t[v].lmx = -INF;
		}
		return;
	}
	int tm = (tl+tr)/2;
	upd(2*v,l,min(r,tm),tl,tm,mode,val);
	upd(2*v+1,max(l,tm+1),r,tm+1,tr,mode,val);
	t[v].mx = max(t[2*v].mx,t[2*v+1].mx);
	t[v].mn = min(t[2*v].mn,t[2*v+1].mn);
}
void query(int v,int l,int r){
	if(l == r){
		ans[l] = t[v].mx;
		return;
	}
	pushdown(v);
	int tm = (l+r)/2;
	query(2*v,l,tm);
	query(2*v+1,tm+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	t.resize(8*(n+1));
	ans.resize(n+1);
  for(int i=0;i<k;i++){
	  left[i]++;
	  right[i]++;
      upd(1,left[i],right[i],1,n,op[i]%2,height[i]);
  }
  query(1,1,n);
  for(int i=0;i<n;i++){
	  finalHeight[i] = ans[i+1];
  }
}
/*
int main()
{
	int n,k;
	cin>>n>>k;
	while(k--){
		int t,l,r,x;
		cin>>t>>l>>r>>x;
		l++;r++;
		upd(1,l,r,1,n,t%2,x);
		cout<<"upd"<<'\n';
		query(1,1,n);
		for(int i=1;i<=n;i++)cout<<ans[i]<<" ";
		cout<<'\n';
	}
}
*/

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39