oj.uz

Submission #265938

# Submission time Handle Problem Language Result Execution time Memory
265938 2020-08-15T05:37:11 Z kaage Bridges (APIO19_bridges) C++17
16 / 100
 835 ms 5608 KB 
#line 2 "/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp"
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx2")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define all(V) V.begin(),V.end()
typedef long long lint;
typedef unsigned long long ulint;
typedef std::pair<int, int> P;
typedef std::pair<lint, lint> LP;
constexpr int INF = INT_MAX/2;
constexpr lint LINF = LLONG_MAX/2;
constexpr double eps = DBL_EPSILON;
constexpr double PI=3.141592653589793238462643383279;
template<class T>
class prique :public std::priority_queue<T, std::vector<T>, std::greater<T>> {};
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
inline lint gcd(lint a, lint b) {
	while (b) {
		lint c = a;
		a = b; b = c % b;
	}
	return a;
}
inline lint lcm(lint a, lint b) {
	return a / gcd(a, b) * b;
}
bool isprime(lint n) {
	if (n == 1)return false;
	for (int i = 2; i * i <= n; i++) {
		if (n % i == 0)return false;
	}
	return true;
}
template<typename T>
T mypow(T a, lint b) {
	T res(1);
	while(b){
		if(b&1)res*=a;
		a*=a;
		b>>=1;
	}
	return res;
}
lint modpow(lint a, lint b, lint m) {
	lint res(1);
	while(b){
		if(b&1){
			res*=a;res%=m;
		}
		a*=a;a%=m;
		b>>=1;
	}
	return res;
}
template<typename T>
void printArray(std::vector<T>& vec) {
	rep(i, vec.size()){
		std::cout << vec[i];
		std::cout<<(i==(int)vec.size()-1?"\n":" ");
	}
}
template<typename T>
void printArray(T l, T r) {
	T rprev = std::prev(r);
	for (T i = l; i != rprev; i++) {
		std::cout << *i << " ";
	}
	std::cout << *rprev << std::endl;
}
LP extGcd(lint a,lint b) {
	if(b==0)return {1,0};
	LP s=extGcd(b,a%b);
	std::swap(s.first,s.second);
	s.second-=a/b*s.first;
	return s;
}
LP ChineseRem(const lint& b1,const lint& m1,const lint& b2,const lint& m2) {
	lint p=extGcd(m1,m2).first;
	lint tmp=(b2-b1)*p%m2;
	lint r=(b1+m1*tmp+m1*m2)%(m1*m2);
	return std::make_pair(r,m1*m2);
}
/*template<typename F>
inline constexpr decltype(auto) lambda_fix(F&& f){
	return [f=std::forward<F>(f)](auto&&... args){
		return f(f,std::forward<decltype(args)>(args)...);
	};
}*/
#line 3 "/Users/kaage/Desktop/ProgrammingWorkspace/library/data-structure/SegTree.hpp"
template<typename T>
class SegTree {
protected:
	unsigned int n = 1, rank = 0;
	std::vector<T> node;
	T nodee;
	virtual T nodef(const T&, const T&)const = 0;
public:
	SegTree(unsigned int m, T init, T nodee):nodee(nodee) {
		while (n < m) {
			n *= 2;
			rank++;
		}
		node.resize(2 * n, nodee);
		for (unsigned int i = n; i < 2 * n; i++)node[i] = init;
	}
	SegTree(const std::vector<T>& initvec, T nodee):nodee(nodee) {
		unsigned int m = initvec.size();
		while (n < m) {
			n *= 2;
			rank++;
		}
		node.resize(2 * n, nodee);
		for (unsigned int i = n; i < 2 * n; i++) {
			if (i - n < m)node[i] = initvec[i - n];
		}
	}
	virtual void update(int i, T x) {
		i += n;
		node[i] = x;
		while (i != 1) {
			i >>= 1;
			node[i] = nodef(node[2 * i], node[2 * i + 1]);
		}
	}
	virtual T query(int l, int r) {
		l += n; r += n;
		T ls = nodee, rs = nodee;
		while (l < r) {
			if (l & 1) {
				ls = nodef(ls, node[l]);
				l++;
			}
			if (r & 1) {
				r--;
				rs = nodef(node[r], rs);
			}
			l >>= 1; r >>= 1;
		}
		return nodef(ls, rs);
	}
	virtual T operator[](const int& x) {
		return node[n + x];
	}
	void print() {
		rep(i, n)std::cout << operator[](i) << " ";
		std::cout << std::endl;
	}
};
class RSQ :public SegTree<lint> {
	lint nodef(const lint& lhs,const lint& rhs)const{return lhs+rhs;}
public:
	RSQ(int size, const lint& def = 0) :SegTree<lint>(size, def, 0) {}
	RSQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, 0) {
		for(int i=n-1;i>0;i--)node[i]=nodef(node[i<<1],node[i<<1|1]);
	}
};
class RMiQ :public SegTree<lint> {
	lint nodef(const lint& lhs,const lint& rhs)const{return std::min(lhs,rhs);}
public:
	RMiQ(int size, const lint& def = 0) :SegTree<lint>(size, def, LINF) {}
	RMiQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, LINF) {
		for(int i=n-1;i>0;i--)node[i]=nodef(node[i<<1],node[i<<1|1]);
	}
};
class RMaQ :public SegTree<lint> {
	lint nodef(const lint& lhs,const lint& rhs)const{return std::max(lhs,rhs);}
public:
	RMaQ(int size, const lint& def = 0) :SegTree<lint>(size, def, -LINF) {}
	RMaQ(const std::vector<lint>& initvec) :SegTree<lint>(initvec, -LINF) {
		for(int i=n-1;i>0;i--)node[i]=nodef(node[i<<1],node[i<<1|1]);
	}
};
#line 3 "main.cpp"
int n,m,q,u[100010],v[100010],d[100010];
int main(){
	std::cin>>n>>m;
	std::vector<lint> vec={INF};
	REP(i,m){
		std::cin>>u[i]>>v[i]>>d[i];
		vec.emplace_back(d[i]);
	}
	RMiQ st(vec);
	std::cin>>q;
	rep(i,q){
		int type;
		std::cin>>type;
		if(type==1){
			int b,r;
			std::cin>>b>>r;
			st.update(b,r);
		}
		else{
			int s,w;
			std::cin>>s>>w;
			int min=0,max=s;
			while(min+1<max){
				int mid=(min+max)/2;
				if(st.query(mid,s)<w)min=mid;
				else max=mid;
			}
			int memo=min;
			min=s-1,max=n;
			while(min+1<max){
				int mid=(min+max)/2;
				if(st.query(s,mid+1)<w)max=mid;
				else min=mid;
			}
			std::cout<<max-memo<<std::endl;
		}
	}
}

Compilation message

/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:3: warning: ignoring #pragma target  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:4: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:5: warning: ignoring #pragma optimize  [-Wunknown-pragmas]

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 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 547 ms 2632 KB Output is correct
2 Correct 511 ms 2908 KB Output is correct
3 Correct 507 ms 2716 KB Output is correct
4 Correct 496 ms 2740 KB Output is correct
5 Correct 496 ms 2672 KB Output is correct
6 Correct 588 ms 4332 KB Output is correct
7 Correct 598 ms 5356 KB Output is correct
8 Correct 579 ms 5360 KB Output is correct
9 Correct 378 ms 1912 KB Output is correct
10 Correct 439 ms 4336 KB Output is correct
11 Correct 445 ms 4388 KB Output is correct
12 Correct 814 ms 5608 KB Output is correct
13 Correct 332 ms 5232 KB Output is correct

Subtask #3
0 / 17.0

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

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 2632 KB Output is correct
2 Correct 511 ms 2908 KB Output is correct
3 Correct 507 ms 2716 KB Output is correct
4 Correct 496 ms 2740 KB Output is correct
5 Correct 496 ms 2672 KB Output is correct
6 Correct 588 ms 4332 KB Output is correct
7 Correct 598 ms 5356 KB Output is correct
8 Correct 579 ms 5360 KB Output is correct
9 Correct 378 ms 1912 KB Output is correct
10 Correct 439 ms 4336 KB Output is correct
11 Correct 445 ms 4388 KB Output is correct
12 Correct 814 ms 5608 KB Output is correct
13 Correct 332 ms 5232 KB Output is correct
14 Incorrect 456 ms 1940 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 384 KB Output isn't correct
2 Halted 0 ms 0 KB -