oj.uz

Submission #423593

# Submission time Handle Problem Language Result Execution time Memory
423593 2021-06-11T10:00:49 Z vulpes2 Crossing (JOI21_crossing) C++17
26 / 100
 5925 ms 122592 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:260:9: note: in expansion of macro 'forr'
  260 |         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:298:9: note: in expansion of macro 'forr'
  298 |         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:306:13: note: in expansion of macro 'forr'
  306 |             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:278: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:271: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

# Verdict Execution time Memory Grader output
1 Correct 713 ms 900 KB Output is correct
2 Correct 831 ms 948 KB Output is correct
3 Correct 876 ms 908 KB Output is correct
4 Correct 688 ms 936 KB Output is correct
5 Correct 682 ms 900 KB Output is correct
6 Correct 615 ms 944 KB Output is correct
7 Correct 727 ms 976 KB Output is correct
8 Correct 666 ms 968 KB Output is correct
9 Correct 685 ms 968 KB Output is correct
10 Correct 737 ms 992 KB Output is correct
11 Correct 683 ms 1092 KB Output is correct
12 Correct 692 ms 1108 KB Output is correct
13 Correct 675 ms 976 KB Output is correct
14 Correct 685 ms 948 KB Output is correct
15 Correct 718 ms 1024 KB Output is correct
16 Correct 720 ms 936 KB Output is correct
17 Correct 683 ms 948 KB Output is correct
18 Correct 782 ms 996 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 900 KB Output is correct
2 Correct 831 ms 948 KB Output is correct
3 Correct 876 ms 908 KB Output is correct
4 Correct 688 ms 936 KB Output is correct
5 Correct 682 ms 900 KB Output is correct
6 Correct 615 ms 944 KB Output is correct
7 Correct 727 ms 976 KB Output is correct
8 Correct 666 ms 968 KB Output is correct
9 Correct 685 ms 968 KB Output is correct
10 Correct 737 ms 992 KB Output is correct
11 Correct 683 ms 1092 KB Output is correct
12 Correct 692 ms 1108 KB Output is correct
13 Correct 675 ms 976 KB Output is correct
14 Correct 685 ms 948 KB Output is correct
15 Correct 718 ms 1024 KB Output is correct
16 Correct 720 ms 936 KB Output is correct
17 Correct 683 ms 948 KB Output is correct
18 Correct 782 ms 996 KB Output is correct
19 Correct 5112 ms 117212 KB Output is correct
20 Correct 4357 ms 117012 KB Output is correct
21 Correct 2337 ms 118384 KB Output is correct
22 Correct 2618 ms 120584 KB Output is correct
23 Correct 1195 ms 8392 KB Output is correct
24 Correct 1233 ms 8428 KB Output is correct
25 Correct 2469 ms 117016 KB Output is correct
26 Correct 2754 ms 117120 KB Output is correct
27 Correct 3364 ms 117028 KB Output is correct
28 Correct 3397 ms 117112 KB Output is correct
29 Correct 3230 ms 117688 KB Output is correct
30 Correct 1378 ms 8452 KB Output is correct
31 Correct 3170 ms 117108 KB Output is correct
32 Correct 3216 ms 119036 KB Output is correct
33 Correct 1320 ms 8408 KB Output is correct
34 Correct 3243 ms 117068 KB Output is correct
35 Correct 2283 ms 122592 KB Output is correct
36 Correct 1266 ms 8352 KB Output is correct
37 Correct 1161 ms 8340 KB Output is correct
38 Correct 4182 ms 117128 KB Output is correct
39 Correct 1567 ms 117020 KB Output is correct
40 Correct 2135 ms 55316 KB Output is correct
41 Correct 5925 ms 117088 KB Output is correct
42 Correct 1569 ms 117004 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 900 KB Output is correct
2 Correct 831 ms 948 KB Output is correct
3 Correct 876 ms 908 KB Output is correct
4 Correct 688 ms 936 KB Output is correct
5 Correct 682 ms 900 KB Output is correct
6 Correct 615 ms 944 KB Output is correct
7 Correct 727 ms 976 KB Output is correct
8 Correct 666 ms 968 KB Output is correct
9 Correct 685 ms 968 KB Output is correct
10 Correct 737 ms 992 KB Output is correct
11 Correct 683 ms 1092 KB Output is correct
12 Correct 692 ms 1108 KB Output is correct
13 Correct 675 ms 976 KB Output is correct
14 Correct 685 ms 948 KB Output is correct
15 Correct 718 ms 1024 KB Output is correct
16 Correct 720 ms 936 KB Output is correct
17 Correct 683 ms 948 KB Output is correct
18 Correct 782 ms 996 KB Output is correct
19 Correct 772 ms 876 KB Output is correct
20 Correct 847 ms 920 KB Output is correct
21 Incorrect 670 ms 900 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 713 ms 900 KB Output is correct
2 Correct 831 ms 948 KB Output is correct
3 Correct 876 ms 908 KB Output is correct
4 Correct 688 ms 936 KB Output is correct
5 Correct 682 ms 900 KB Output is correct
6 Correct 615 ms 944 KB Output is correct
7 Correct 727 ms 976 KB Output is correct
8 Correct 666 ms 968 KB Output is correct
9 Correct 685 ms 968 KB Output is correct
10 Correct 737 ms 992 KB Output is correct
11 Correct 683 ms 1092 KB Output is correct
12 Correct 692 ms 1108 KB Output is correct
13 Correct 675 ms 976 KB Output is correct
14 Correct 685 ms 948 KB Output is correct
15 Correct 718 ms 1024 KB Output is correct
16 Correct 720 ms 936 KB Output is correct
17 Correct 683 ms 948 KB Output is correct
18 Correct 782 ms 996 KB Output is correct
19 Correct 5112 ms 117212 KB Output is correct
20 Correct 4357 ms 117012 KB Output is correct
21 Correct 2337 ms 118384 KB Output is correct
22 Correct 2618 ms 120584 KB Output is correct
23 Correct 1195 ms 8392 KB Output is correct
24 Correct 1233 ms 8428 KB Output is correct
25 Correct 2469 ms 117016 KB Output is correct
26 Correct 2754 ms 117120 KB Output is correct
27 Correct 3364 ms 117028 KB Output is correct
28 Correct 3397 ms 117112 KB Output is correct
29 Correct 3230 ms 117688 KB Output is correct
30 Correct 1378 ms 8452 KB Output is correct
31 Correct 3170 ms 117108 KB Output is correct
32 Correct 3216 ms 119036 KB Output is correct
33 Correct 1320 ms 8408 KB Output is correct
34 Correct 3243 ms 117068 KB Output is correct
35 Correct 2283 ms 122592 KB Output is correct
36 Correct 1266 ms 8352 KB Output is correct
37 Correct 1161 ms 8340 KB Output is correct
38 Correct 4182 ms 117128 KB Output is correct
39 Correct 1567 ms 117020 KB Output is correct
40 Correct 2135 ms 55316 KB Output is correct
41 Correct 5925 ms 117088 KB Output is correct
42 Correct 1569 ms 117004 KB Output is correct
43 Correct 772 ms 876 KB Output is correct
44 Correct 847 ms 920 KB Output is correct
45 Incorrect 670 ms 900 KB Output isn't correct
46 Halted 0 ms 0 KB -