Submission #718720

#	Time	Username	Problem	Language	Result	Execution time	Memory
718720		mseebacher	Wall (IOI14_wall)	C++17	0 / 100	2 ms	2644 KiB

wall

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5
#define pb(x) push_back(x)
#define inf 1e9+10

vector<int> ad[MAXI];
vector<bool> vis(MAXI,0);


void dfs(int x){
	if(vis[x]) return;
	vis[x] = 1;
	for(auto s:ad[x]){
		dfs(s);
	}
}

void setIO(string s) {
	freopen((s + ".in").c_str(), "r", stdin);
	freopen((s + ".out").c_str(), "w", stdout);
}  

int* dummy;

struct Node{
	int mx;
	int mn;
};

struct segtree{
	int size = 0;
	vector<Node> tree;
	vector<bool> marked;
	
	void init(int n){
		int x = 1;
		while(x < n) x*=2;
		size = x;
		Node a;
		a.mx = inf;
		a.mn = 0;
		tree.assign(2*size,a);
		marked.assign(2*size,0);
	}
	// x1 child, x2 parent
	Node combine(Node u,Node p){
		u.mx = max(u.mx,p.mn);
		u.mx = min(u.mx,p.mx);
		u.mn = max(p.mn,u.mn);
		u.mn = min(u.mn,p.mx);
		return u;
	}
	
	
	void push(int x){
		tree[2*x] = combine(tree[2*x],tree[x]);
		tree[2*x+1] = combine(tree[2*x+1],tree[x]);
		marked[x] = 0;
		marked[2*x] = marked[2*x+1] = 1;
		tree[x].mx = inf;
		tree[x].mn = 0;
	}
	
	void update(int op, int h,int l,int r,int x,int lx,int rx){
		if(l > r) return;
		if(l > rx || r < lx) return;
		if(lx >= l && rx <= r){
			if(op == 1){
				tree[x].mn = max(tree[x].mn,h);
				tree[x].mx = max(tree[x].mn,tree[x].mx);
			}
			else{
				tree[x].mx = min(tree[x].mx,h);
				tree[x].mn = min(tree[x].mn,tree[x].mx);	
			}
			//cout << tree[x].mn << " " << tree[x].mx << "\n";
			marked[x] = 1;
			
			return;
		}
		if(marked[x])push(x);
		
		int m = (lx+rx) >> 1;
		update(op,h,l,r,2*x,lx,m);
		update(op,h,l,r,2*x+1,m+1,rx);
	}
	
	void get(int i,int x,int lx,int rx){
		if(lx == rx){
			dummy[i] = min(max(0,tree[x].mn),tree[x].mx);
			return;
		}
		push(x);
		int mid = (lx+rx) >> 1;
		if(i <= mid) get(i,2*x,lx,mid);
		else get(i,2*x+1,mid+1,rx);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	segtree s;
	s.init(4*n);
	dummy = finalHeight;
	for(int i = 0;i<k;i++){
		s.update(op[i],height[i],left[i],right[i],1,0,s.size-1);
	}
	
	for(int i = 0;i<n;i++){
		s.get(i,1,0,s.size-1);
		
	}
	for(int i = 0;i<n;i++){
		cout << finalHeight[i] << " ";
	}
}

Compilation message (stderr)

wall.cpp: In function 'void setIO(std::string)':
wall.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wall.cpp:24:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  freopen((s + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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