oj.uz

Submission #568950

# Submission time Handle Problem Language Result Execution time Memory
568950 2022-05-26T11:33:09 Z HappyPacMan Bridges (APIO19_bridges) C++14
16 / 100
 689 ms 3780 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 2;
const int inf = 1e9;
int seg[4*maxn];

void upd(int i,int l,int r,int u,int v){
	if(l == r){
		seg[i] = v;
	}else{
		int m = (l+r)/2;
		if(u <= m){
			upd(i<<1,l,m,u,v);
		}else{
			upd(i<<1|1,m+1,r,u,v);
		}
		seg[i] = min(seg[i<<1],seg[i<<1|1]);
	}
}
int qry(int i,int l,int r,int ql,int qr){
	if(l > qr || r < ql){
		return inf;
	}else if(ql <= l && r <= qr){
		return seg[i];
	}else{
		int m = (l+r)/2;
		return min(qry(i<<1,l,m,ql,qr),qry(i<<1|1,m+1,r,ql,qr));
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n,m;
	cin >> n >> m;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin >> u >> v >> w;
		upd(1,1,m,i,w);
	}
	int q;
	cin >> q;
	while(q--){
		int t,x,y;
		cin >> t >> x >> y;
		if(t == 1){
			upd(1,1,m,x,y);
		}else{
			int res = 1;
			int li = 1, ri = x;
			while(li < ri){
				int mi = (li+ri)/2;
				if(qry(1,1,m,mi,x-1) >= y){
					ri = mi;
				}else{
					li = mi+1;
				}
			}
			res += x-li;
			int lj = x-1, rj = m;
			while(lj < rj){
				int mj = (lj+rj+1)/2;
				if(qry(1,1,m,x,mj) >= y){
					lj = mj;
				}else{
					rj = mj-1;
				}
			}
			res += lj-x+1;
			cout << res << '\n';
		}
	}
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 1420 KB Output is correct
2 Correct 348 ms 1104 KB Output is correct
3 Correct 355 ms 1396 KB Output is correct
4 Correct 387 ms 1148 KB Output is correct
5 Correct 346 ms 1296 KB Output is correct
6 Correct 426 ms 2388 KB Output is correct
7 Correct 389 ms 3640 KB Output is correct
8 Correct 425 ms 3552 KB Output is correct
9 Correct 26 ms 1868 KB Output is correct
10 Correct 389 ms 2612 KB Output is correct
11 Correct 375 ms 2740 KB Output is correct
12 Correct 689 ms 3780 KB Output is correct
13 Correct 135 ms 3604 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 324 ms 920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 1820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 1420 KB Output is correct
2 Correct 348 ms 1104 KB Output is correct
3 Correct 355 ms 1396 KB Output is correct
4 Correct 387 ms 1148 KB Output is correct
5 Correct 346 ms 1296 KB Output is correct
6 Correct 426 ms 2388 KB Output is correct
7 Correct 389 ms 3640 KB Output is correct
8 Correct 425 ms 3552 KB Output is correct
9 Correct 26 ms 1868 KB Output is correct
10 Correct 389 ms 2612 KB Output is correct
11 Correct 375 ms 2740 KB Output is correct
12 Correct 689 ms 3780 KB Output is correct
13 Correct 135 ms 3604 KB Output is correct
14 Incorrect 324 ms 920 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -