oj.uz

답안 #423580

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423580 2021-06-11T09:54:13 Z vulpes2 Crossing (JOI21_crossing) C++17
26 / 100
 7000 ms 1022428 KB 
//#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;
}

Compilation message

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;  }
      |                 ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2907 ms 1320 KB Output is correct
2 Correct 3544 ms 1604 KB Output is correct
3 Correct 4011 ms 1476 KB Output is correct
4 Correct 3198 ms 1548 KB Output is correct
5 Correct 3203 ms 1492 KB Output is correct
6 Correct 2451 ms 1376 KB Output is correct
7 Correct 3105 ms 1368 KB Output is correct
8 Correct 2907 ms 1328 KB Output is correct
9 Correct 2934 ms 1400 KB Output is correct
10 Correct 2900 ms 1412 KB Output is correct
11 Correct 3000 ms 1540 KB Output is correct
12 Correct 2843 ms 1476 KB Output is correct
13 Correct 2972 ms 1348 KB Output is correct
14 Correct 2855 ms 1404 KB Output is correct
15 Correct 2897 ms 1332 KB Output is correct
16 Correct 2910 ms 1340 KB Output is correct
17 Correct 3006 ms 1340 KB Output is correct
18 Correct 3838 ms 1576 KB Output is correct

Subtask #2
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2907 ms 1320 KB Output is correct
2 Correct 3544 ms 1604 KB Output is correct
3 Correct 4011 ms 1476 KB Output is correct
4 Correct 3198 ms 1548 KB Output is correct
5 Correct 3203 ms 1492 KB Output is correct
6 Correct 2451 ms 1376 KB Output is correct
7 Correct 3105 ms 1368 KB Output is correct
8 Correct 2907 ms 1328 KB Output is correct
9 Correct 2934 ms 1400 KB Output is correct
10 Correct 2900 ms 1412 KB Output is correct
11 Correct 3000 ms 1540 KB Output is correct
12 Correct 2843 ms 1476 KB Output is correct
13 Correct 2972 ms 1348 KB Output is correct
14 Correct 2855 ms 1404 KB Output is correct
15 Correct 2897 ms 1332 KB Output is correct
16 Correct 2910 ms 1340 KB Output is correct
17 Correct 3006 ms 1340 KB Output is correct
18 Correct 3838 ms 1576 KB Output is correct
19 Execution timed out 7081 ms 1022428 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2907 ms 1320 KB Output is correct
2 Correct 3544 ms 1604 KB Output is correct
3 Correct 4011 ms 1476 KB Output is correct
4 Correct 3198 ms 1548 KB Output is correct
5 Correct 3203 ms 1492 KB Output is correct
6 Correct 2451 ms 1376 KB Output is correct
7 Correct 3105 ms 1368 KB Output is correct
8 Correct 2907 ms 1328 KB Output is correct
9 Correct 2934 ms 1400 KB Output is correct
10 Correct 2900 ms 1412 KB Output is correct
11 Correct 3000 ms 1540 KB Output is correct
12 Correct 2843 ms 1476 KB Output is correct
13 Correct 2972 ms 1348 KB Output is correct
14 Correct 2855 ms 1404 KB Output is correct
15 Correct 2897 ms 1332 KB Output is correct
16 Correct 2910 ms 1340 KB Output is correct
17 Correct 3006 ms 1340 KB Output is correct
18 Correct 3838 ms 1576 KB Output is correct
19 Correct 3446 ms 1480 KB Output is correct
20 Correct 4030 ms 1316 KB Output is correct
21 Correct 3163 ms 1336 KB Output is correct
22 Correct 2678 ms 1488 KB Output is correct
23 Correct 2869 ms 1344 KB Output is correct
24 Correct 2874 ms 1376 KB Output is correct
25 Correct 2948 ms 1332 KB Output is correct
26 Correct 3025 ms 1336 KB Output is correct
27 Correct 2951 ms 1340 KB Output is correct
28 Correct 2992 ms 1388 KB Output is correct
29 Correct 3079 ms 1572 KB Output is correct
30 Correct 2788 ms 1320 KB Output is correct
31 Correct 2939 ms 1484 KB Output is correct
32 Correct 3208 ms 1400 KB Output is correct
33 Correct 3336 ms 1380 KB Output is correct
34 Correct 2614 ms 1372 KB Output is correct
35 Correct 3130 ms 1412 KB Output is correct
36 Correct 3068 ms 1408 KB Output is correct
37 Correct 2874 ms 1424 KB Output is correct
38 Correct 2898 ms 1312 KB Output is correct
39 Correct 2985 ms 1468 KB Output is correct
40 Correct 3040 ms 1524 KB Output is correct
41 Correct 3008 ms 1456 KB Output is correct
42 Correct 2935 ms 1364 KB Output is correct
43 Correct 2976 ms 1432 KB Output is correct
44 Correct 2968 ms 1468 KB Output is correct

Subtask #4
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2907 ms 1320 KB Output is correct
2 Correct 3544 ms 1604 KB Output is correct
3 Correct 4011 ms 1476 KB Output is correct
4 Correct 3198 ms 1548 KB Output is correct
5 Correct 3203 ms 1492 KB Output is correct
6 Correct 2451 ms 1376 KB Output is correct
7 Correct 3105 ms 1368 KB Output is correct
8 Correct 2907 ms 1328 KB Output is correct
9 Correct 2934 ms 1400 KB Output is correct
10 Correct 2900 ms 1412 KB Output is correct
11 Correct 3000 ms 1540 KB Output is correct
12 Correct 2843 ms 1476 KB Output is correct
13 Correct 2972 ms 1348 KB Output is correct
14 Correct 2855 ms 1404 KB Output is correct
15 Correct 2897 ms 1332 KB Output is correct
16 Correct 2910 ms 1340 KB Output is correct
17 Correct 3006 ms 1340 KB Output is correct
18 Correct 3838 ms 1576 KB Output is correct
19 Execution timed out 7081 ms 1022428 KB Time limit exceeded
20 Halted 0 ms 0 KB -