oj.uz

답안 #266164

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
266164 2020-08-15T06:54:55 Z kaage 가로등 (APIO19_street_lamps) C++17
20 / 100
 897 ms 27532 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/graph/UnionFind.hpp"
class UnionFind {
protected:
	std::vector<int> par, size;
public:
	UnionFind(){}
	UnionFind(int size) {init(size);}
	void init(int size){
		par.resize(size); this->size.resize(size, 1);
		rep(i, size) {
			par[i] = i;
		}
	}
	int find(int n) {
		if (par[n] == n)return n;
		return par[n] = find(par[n]);
	}
	void unite(int n, int m) {
		n = find(n);
		m = find(m);
		if (n == m)return;
		int a=n,b=m;
		if(size[a]>size[b])std::swap(a,b);
		par[a] = b;
		size[b] += size[a];
	}
	bool same(int n, int m) {
		return find(n) == find(m);
	}
	int getsize(int n) {
		return size[find(n)];
	}
};
#line 3 "main.cpp"
int n,q,a[300010],b[300010],last[300010],ans[300010],t[300010];
std::string s,type[300010];
std::vector<int> opindex;
bool flag[300010];
int min[300010],max[300010];
int main(){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cin>>n>>q>>s;
	UnionFind fuf1(n+1),fuf2(n+1);
	rep(i,s.size()){
		if(s[i]=='1'){
			fuf1.unite(i,i+1);
			fuf2.unite(i,i+1);
		}
	}
	int opcount=0;
	rep(i,q){
		std::cin>>type[i];
		if(type[i]=="query"){
			std::cin>>a[i]>>b[i];
			a[i]--;b[i]--;
			min[i]=-1,max[i]=opcount;
			if(!fuf1.same(a[i],b[i]))max[i]=-1;
			if(fuf2.same(a[i],b[i]))max[i]=INF;
		}
		else{
			std::cin>>t[i];
			t[i]--;
			fuf1.unite(t[i],t[i]+1);
			opcount++;
			opindex.emplace_back(i);
		}
	}
	while(true){
		std::vector<P> mid;
		rep(i,q){
			if(type[i]=="query"&&min[i]+1<max[i]&&max[i]!=INF){
				mid.emplace_back((min[i]+max[i])/2,i);
			}
		}
		if(mid.empty())break;
		std::sort(all(mid));
		UnionFind uf(n+1);
		rep(i,s.size()){
			if(s[i]=='1')uf.unite(i,i+1);
		}
		int cnt=0,now=0;
		rep(i,q){
			while(now<mid.size()&&cnt==mid[now].first){
				if(uf.same(a[mid[now].second],b[mid[now].second])){
					max[mid[now].second]=mid[now].first;
				}
				else min[mid[now].second]=mid[now].first;
				now++;
			}
			if(type[i]=="toggle"){
				uf.unite(t[i],t[i]+1);
				cnt++;
			}
		}
	}
	rep(i,q){
		if(type[i]=="query"){
			if(max[i]!=-1&&max[i]!=INF){
				//std::cout<<max[i]<<std::endl;
				std::cout<<i-opindex[min[i]]<<std::endl;
			}
			else if(max[i]==INF)std::cout<<i+1<<std::endl;
			else std::cout<<0<<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]
main.cpp: In function 'int main()':
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
main.cpp:13:2: note: in expansion of macro 'rep'
/Users/kaage/Desktop/ProgrammingWorkspace/library/other/template.hpp:33:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
main.cpp:47:3: note: in expansion of macro 'rep'
main.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 819 ms 18180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 9856 KB Output is correct
2 Correct 8 ms 9856 KB Output is correct
3 Correct 9 ms 9856 KB Output is correct
4 Correct 14 ms 9728 KB Output is correct
5 Correct 555 ms 24320 KB Output is correct
6 Correct 750 ms 24028 KB Output is correct
7 Correct 897 ms 23688 KB Output is correct
8 Correct 795 ms 26892 KB Output is correct
9 Correct 685 ms 18268 KB Output is correct
10 Correct 750 ms 19308 KB Output is correct
11 Correct 729 ms 19052 KB Output is correct
12 Correct 845 ms 26252 KB Output is correct
13 Correct 797 ms 27532 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 9728 KB Output is correct
2 Incorrect 9 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 9728 KB Output isn't correct
2 Halted 0 ms 0 KB -