oj.uz

Submission #718705

# Submission time Handle Problem Language Result Execution time Memory
718705 2023-04-04T14:31:02 Z mseebacher Wall (IOI14_wall) C++17
100 / 100
 864 ms 162296 KB 
#include <bits/stdc++.h>
#include "wall.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;
			if(lx == rx){
				dummy[lx] = min(max(0,tree[x].mn),tree[x].mx);
			}
			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 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.update(1,0,i,i,1,0,s.size-1);
		
	}
	
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 5 ms 2804 KB Output is correct
3 Correct 3 ms 2676 KB Output is correct
4 Correct 8 ms 3904 KB Output is correct
5 Correct 7 ms 3796 KB Output is correct
6 Correct 7 ms 3844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 159 ms 16308 KB Output is correct
3 Correct 188 ms 11852 KB Output is correct
4 Correct 502 ms 28900 KB Output is correct
5 Correct 258 ms 29396 KB Output is correct
6 Correct 249 ms 27724 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 3 ms 2780 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 8 ms 3828 KB Output is correct
5 Correct 7 ms 3880 KB Output is correct
6 Correct 7 ms 3796 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 150 ms 16188 KB Output is correct
9 Correct 169 ms 11852 KB Output is correct
10 Correct 480 ms 28852 KB Output is correct
11 Correct 253 ms 29492 KB Output is correct
12 Correct 239 ms 27744 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 150 ms 16232 KB Output is correct
15 Correct 31 ms 5788 KB Output is correct
16 Correct 486 ms 28856 KB Output is correct
17 Correct 248 ms 28268 KB Output is correct
18 Correct 239 ms 28204 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 3 ms 2800 KB Output is correct
3 Correct 3 ms 2644 KB Output is correct
4 Correct 9 ms 3796 KB Output is correct
5 Correct 9 ms 3820 KB Output is correct
6 Correct 8 ms 3800 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 142 ms 16204 KB Output is correct
9 Correct 170 ms 11948 KB Output is correct
10 Correct 479 ms 28852 KB Output is correct
11 Correct 270 ms 29404 KB Output is correct
12 Correct 269 ms 27948 KB Output is correct
13 Correct 2 ms 2664 KB Output is correct
14 Correct 172 ms 16204 KB Output is correct
15 Correct 32 ms 5788 KB Output is correct
16 Correct 490 ms 28852 KB Output is correct
17 Correct 242 ms 28264 KB Output is correct
18 Correct 243 ms 28276 KB Output is correct
19 Correct 864 ms 162240 KB Output is correct
20 Correct 862 ms 162128 KB Output is correct
21 Correct 858 ms 162152 KB Output is correct
22 Correct 858 ms 162028 KB Output is correct
23 Correct 854 ms 162128 KB Output is correct
24 Correct 847 ms 162172 KB Output is correct
25 Correct 845 ms 162164 KB Output is correct
26 Correct 844 ms 162124 KB Output is correct
27 Correct 844 ms 162296 KB Output is correct
28 Correct 844 ms 162152 KB Output is correct
29 Correct 848 ms 162084 KB Output is correct
30 Correct 853 ms 162164 KB Output is correct