제출 #423580

#제출 시각아이디문제언어결과실행 시간메모리
423580vulpes2Crossing (JOI21_crossing)C++17
26 / 100
7081 ms1022428 KiB
//#include <atcoder/maxflow.hpp> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> #include <iostream> #include <map> #include <list> #include <set> #include <algorithm> #include <vector> #include <string> #include <functional> #include <queue> #include <deque> #include <stack> #include <unordered_map> #include <unordered_set> #include <cmath> #include <iterator> #include <random> #include <chrono> #include <complex> #include <bitset> #include <fstream> #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i) #define set_map_includes(set, elt) (set.find((elt)) != set.end()) #define readint(i) int i; cin >> i #define readll(i) ll i; cin >> i #define readdouble(i) double i; cin >> i #define readstring(s) string s; cin >> s typedef long long ll; //using namespace __gnu_pbds; //using namespace atcoder; using namespace std; const ll modd = (1000LL * 1000LL * 1000LL + 7LL); //const ll modd = 998244353; template<class T> class SegmentTree2 { public: int B; // power of two greater than size of input data SegmentTree2(const vector<T>& data, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) { Initialize(data); } SegmentTree2(int n, function<T(T,T)> f_, T zero_value = 0) : zv(zero_value), f(f_) { vector<T> temp(n, zv); Initialize(temp); } T operator[](int i) { return tree[B+i]; } T GetEvaluation(int L, int R) { // "min/max" on interval [L,R); 0-based indexing, as usual if (R<=L) { return zv; } return GetEvaluationHelper(L, R, 0, B, 1); } void SetVal(int i, T val) { tree[B+i] = val; for(int j = (B + i) / 2; j >= 1; j /= 2) { tree[j] = f(tree[2*j], tree[2*j+1]); } } private: vector<T> tree; T zv; function<T(T,T)> f; void Initialize(const vector<T>& data) { B = 1; while(B < data.size()) {B *= 2; } tree = std::move(vector<T>(2*B, zv)); copy(data.begin(), data.end(), next(tree.begin(), B)); for(int i = B - 1; i >= 1; --i) { tree[i] = f(tree[2*i], tree[2*i+1]); } } T GetEvaluationHelper(int L, int R, int start, int length, int tree_index) { if (L==R) { return zv; } if ((L==start) && (R==start+length)) { return tree[tree_index]; } int midpoint = start + length/2; T left_ = zv, right_ = zv; if (L<=min(midpoint,R)) { left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index); } if (max(midpoint,L)<=R) { right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1); } return f(left_, right_); } }; template<class T, class S> class LazySegmentTree { // Lazy propagation segment tree, containing elts of type T; S is type ("paramter space type") for all possible function we'll be // applying to elts (thee funcs should commute with f; f should be associative) public: typedef function<T(T)> application_type; // f is combining function, should be associative; zero_value is identity for f as a grupoid operation; // com is composition of application functions, specifically com(a1, a2) is a1 \circ a2 ie com(a1,a2)(t)=a1(a2(t)) // param is parametrization of application functions // id_ is parameter for identity application function // typical example if you have min segtree, and you want to assign values in a lazy way to interval: // T=int,S=int, f(x,y) = min(x,y), zero_value = +infty"=modd"; com(a,b)=a; // param(a) = [](int a){ return function<int(int)>([](int x){return a;}); } // CAREFUL!!!! in param make sure if you capture anything in return function, you do it by value, not by reference!!!!!!!!!!!!!!!!!!! // id_ = say modd+1; and param(modd+1) should be identity, and comm should accomodate that LazySegmentTree(const vector<T>& data, function<T(T,T)> f_, T zero_value, function<S(S,S)> com, function<application_type(S)> param, S id_) : zv(zero_value), f(f_), composition(com), paramtrization(param), ident(id_) { Initialize(data); } T operator[](int i) { return GetEvaluation(i, i+1); } T GetEvaluation(int L, int R) { // "min/max" on interval [L,R); 0-based indexing, as usual if (R<=L) { return zv; } return GetEvaluationHelper(L, R, 0, B, 1, ident); } void SetVal(int L, int R, S g) { // set on interval [L,R); 0-based indexing if (R<=L) { return; } SetValHelper(L, R, 0, B, 1, g); } private: vector<T> tree; vector<S> application_function_below; int B; // power of two greater than size of input data T zv; function<T(T,T)> f; function<S(S,S)> composition; function<application_type(S)> paramtrization; S ident; void Initialize(const vector<T>& data) { B = 1; while(B < data.size()) {B *= 2; } tree = vector<T>(2*B, zv); copy(data.begin(), data.end(), next(tree.begin(), B)); for(int i = B - 1; i >= 1; --i) { tree[i] = f(tree[2*i], tree[2*i+1]); } application_function_below = vector<S>(2*B, ident); } T GetEvaluationHelper(int L, int R, int start, int length, int tree_index, S accumulate) { if (L==R) { return zv; } if ((L==start) && (R==start+length)) { return paramtrization(accumulate)(tree[tree_index]); } int midpoint = start + length/2; T left_ = zv, right_ = zv; if (L<=min(midpoint,R)) { left_ = GetEvaluationHelper(L, min(midpoint,R), start, length/2, 2*tree_index, composition(accumulate, application_function_below[tree_index])); } if (max(midpoint,L)<=R) { right_ = GetEvaluationHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1, composition(accumulate, application_function_below[tree_index])); } return f(left_, right_); } void SetValHelper(int L, int R, int start, int length, int tree_index, S g) { if (L==R) { return; } if ((L==start) && (R==start+length)) { tree[tree_index] = paramtrization(g)(tree[tree_index]); application_function_below[tree_index] = composition(g, application_function_below[tree_index]); return; } int midpoint = start + length/2; application_function_below[2*tree_index] = composition(application_function_below[tree_index], application_function_below[2*tree_index]); application_function_below[2*tree_index+1] = composition(application_function_below[tree_index], application_function_below[2*tree_index+1]); tree[2*tree_index] = paramtrization(application_function_below[tree_index])(tree[2*tree_index]); tree[2*tree_index+1] = paramtrization(application_function_below[tree_index])(tree[2*tree_index+1]); application_function_below[tree_index] = ident; if (L<=min(midpoint,R)) { SetValHelper(L, min(midpoint,R), start, length/2, 2*tree_index, g); } if (max(midpoint,L)<=R) { SetValHelper(max(midpoint,L), R, midpoint, length/2, 2*tree_index+1, g); } tree[tree_index] = f(tree[2*tree_index], tree[2*tree_index+1]); } }; string cross(const string& a, const string& b) { string ret; map<pair<char,char>,char> op; op[make_pair('J', 'J')] = 'J'; op[make_pair('O', 'O')] = 'O'; op[make_pair('I', 'I')] = 'I'; op[make_pair('J', 'O')] = 'I'; op[make_pair('O', 'I')] = 'J'; op[make_pair('I', 'J')] = 'O'; op[make_pair('O', 'J')] = 'I'; op[make_pair('I', 'O')] = 'J'; op[make_pair('J', 'I')] = 'O'; forr(i,0,a.size()) { ret.push_back(op[make_pair(a[i], b[i])]); } return ret; } vector<string> goal; vector<map<tuple<int,int,char>, bool>> val(9); int main(int argc, char *argv[]) { mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution<int> rand_gen(0, modd); // rand_gen(rng) gets the rand no ios_base::sync_with_stdio(false); cin.tie(0); cout.precision(12); // readint(test_cases); int test_cases = 1; forr(t, 1, test_cases) { readint(n); readstring(s1); readstring(s2); readstring(s3); goal.push_back(s1); goal.push_back(s2); goal.push_back(s3); goal.push_back(cross(goal[0], goal[1])); goal.push_back(cross(goal[1], goal[2])); goal.push_back(cross(goal[2], goal[0])); goal.push_back(cross(goal[0], goal[4])); goal.push_back(cross(goal[1], goal[5])); goal.push_back(cross(goal[2], goal[3])); readint(q); vector<bool> ans(q, false); readstring(s); struct eq { int l,r; bool equal; }; vector<LazySegmentTree<eq, char>> lseg; forr(j,0,goal.size()) { vector<eq> segs; forr(i,0,n) { segs.push_back(eq{i, i+1, goal[j][i]==s[i]}); } lseg.emplace_back(segs, [](eq a, eq b){ return eq{a.l,b.r,a.equal&&b.equal}; }, eq{0,0,true}, [](char c1, char c2){ if (c1=='Q') return c2; else return c1; }, [j](char a) { return [a,j](eq x) { if (a=='Q') return x; else { return eq{x.l, x.r, val[j][make_tuple(x.l,x.r, a)]}; } }; }, 'Q' ); SegmentTree2<char> temp(vector<char>(goal[j].begin(), goal[j].end()), [](char x, char y) { if (x=='*') { return y; } if (y=='*') { return x; } if (x=='0') { return '0'; } if (y=='0') { return '0'; } if (x==y) { return x; } else { return '0'; } }, '*'); int B = temp.B; while (B>0) { for(int i = 0; i < temp.B; i += B) { val[j][make_tuple(i, i + B, 'I')] = false; val[j][make_tuple(i, i + B, 'J')] = false; val[j][make_tuple(i, i + B, 'O')] = false; if (temp.GetEvaluation(i, i+B)!='0') { val[j][make_tuple(i, i+B, temp.GetEvaluation(i, i+B))] = true; } } B /= 2; } } // for(auto x : val[0]) { // cout << get<0>(x.first) << " " << get<1>(x.first) << " " << get<2>(x.first) << ": " << x.second << endl; // } bool ret = false; forr(j,0,goal.size()) { ret |= lseg[j].GetEvaluation(0, n).equal; } cout << (ret ? "Yes" : "No") << endl; forr(i,0,q) { readint(l); readint(r); readstring(ch); --l; bool rett = false; forr(j,0,goal.size()) { lseg[j].SetVal(l, r, ch[0]); rett |= lseg[j].GetEvaluation(0, n).equal; } cout << (rett ? "Yes" : "No") << endl; } } return 0; }

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'std::string cross(const string&, const string&)':
Main.cpp:28:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:218:5: note: in expansion of macro 'forr'
  218 |     forr(i,0,a.size()) {
      |     ^~~~
Main.cpp: In function 'int main(int, char**)':
Main.cpp:28:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:259:9: note: in expansion of macro 'forr'
  259 |         forr(j,0,goal.size()) {
      |         ^~~~
Main.cpp:28:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:297:9: note: in expansion of macro 'forr'
  297 |         forr(j,0,goal.size()) {
      |         ^~~~
Main.cpp:28:53: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 | #define forr(i,start,count) for (int i = (start); i < (start)+(count); ++i)
      |                                                     ^
Main.cpp:305:13: note: in expansion of macro 'forr'
  305 |             forr(j,0,goal.size()) {
      |             ^~~~
Main.cpp: In instantiation of 'void SegmentTree2<T>::Initialize(const std::vector<_Tp>&) [with T = char]':
Main.cpp:51:11:   required from 'SegmentTree2<T>::SegmentTree2(const std::vector<_Tp>&, std::function<T(T, T)>, T) [with T = char]'
Main.cpp:277:19:   required from here
Main.cpp:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<char, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |           while(B < data.size()) {B *= 2;  }
      |                 ~~^~~~~~~~~~~~~
Main.cpp: In instantiation of 'void LazySegmentTree<T, S>::Initialize(const std::vector<_Tp>&) [with T = main(int, char**)::eq; S = char]':
Main.cpp:129:11:   required from 'LazySegmentTree<T, S>::LazySegmentTree(const std::vector<_Tp>&, std::function<T(T, T)>, T, std::function<S(S, S)>, std::function<std::function<T(T)>(S)>, S) [with T = main(int, char**)::eq; S = char]'
/usr/include/c++/10/ext/new_allocator.h:150:4:   required from 'void __gnu_cxx::new_allocator<_Tp>::construct(_Up*, _Args&& ...) [with _Up = LazySegmentTree<main(int, char**)::eq, char>; _Args = {std::vector<main(int, char**)::eq, std::allocator<main(int, char**)::eq> >&, main(int, char**)::<lambda(main(int, char**)::eq, main(int, char**)::eq)>, main(int, char**)::eq, main(int, char**)::<lambda(char, char)>, main(int, char**)::<lambda(char)>, char}; _Tp = LazySegmentTree<main(int, char**)::eq, char>]'
/usr/include/c++/10/bits/alloc_traits.h:512:17:   required from 'static void std::allocator_traits<std::allocator<_CharT> >::construct(std::allocator_traits<std::allocator<_CharT> >::allocator_type&, _Up*, _Args&& ...) [with _Up = LazySegmentTree<main(int, char**)::eq, char>; _Args = {std::vector<main(int, char**)::eq, std::allocator<main(int, char**)::eq> >&, main(int, char**)::<lambda(main(int, char**)::eq, main(int, char**)::eq)>, main(int, char**)::eq, main(int, char**)::<lambda(char, char)>, main(int, char**)::<lambda(char)>, char}; _Tp = LazySegmentTree<main(int, char**)::eq, char>; std::allocator_traits<std::allocator<_CharT> >::allocator_type = std::allocator<LazySegmentTree<main(int, char**)::eq, char> >]'
/usr/include/c++/10/bits/vector.tcc:115:30:   required from 'std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::emplace_back(_Args&& ...) [with _Args = {std::vector<main(int, char**)::eq, std::allocator<main(int, char**)::eq> >&, main(int, char**)::<lambda(main(int, char**)::eq, main(int, char**)::eq)>, main(int, char**)::eq, main(int, char**)::<lambda(char, char)>, main(int, char**)::<lambda(char)>, char}; _Tp = LazySegmentTree<main(int, char**)::eq, char>; _Alloc = std::allocator<LazySegmentTree<main(int, char**)::eq, char> >; std::vector<_Tp, _Alloc>::reference = LazySegmentTree<main(int, char**)::eq, char>&]'
Main.cpp:270:13:   required from here
Main.cpp:158:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<main(int, char**)::eq>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |           while(B < data.size()) {B *= 2;  }
      |                 ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...