Submission #445041

#TimeUsernameProblemLanguageResultExecution timeMemory
445041arnold518Crossing (JOI21_crossing)C++17
49 / 100
389 ms23044 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const ll MOD = 1e9+7; int N, Q; char S[MAXN+10]; vector<int> A[3], B; vector<ll> V; ll ppow[MAXN+10]; vector<int> read() { scanf(" %s", S); vector<int> ans; for(int i=0; i<N; i++) { if(S[i]=='J') ans.push_back(0); else if(S[i]=='O') ans.push_back(1); else if(S[i]=='I') ans.push_back(2); } return ans; } ll gethash(vector<int> V) { ll ret=0; for(int i=0; i<N; i++) { ret=(ret+(V[i]+1)*ppow[i])%MOD; } return ret; } struct SEG { ll tree[MAXN*4+10], lazy[MAXN*4+10], sum[MAXN*4+10]; void init(int node, int tl, int tr, vector<int> &V) { if(tl==tr) { tree[node]=(V[tl]+1)*ppow[tl]%MOD; sum[node]=ppow[tl]%MOD; lazy[node]=0; return; } int mid=tl+tr>>1; init(node*2, tl, mid, V); init(node*2+1, mid+1, tr, V); tree[node]=(tree[node*2]+tree[node*2+1])%MOD; sum[node]=(sum[node*2]+sum[node*2+1])%MOD; lazy[node]=0; } void busy(int node, int tl, int tr) { if(lazy[node]==0) return; tree[node]=lazy[node]*sum[node]%MOD; if(tl==tr) { lazy[node]=0; return; } lazy[node*2]=lazy[node]; lazy[node*2+1]=lazy[node]; lazy[node]=0; } void update(int node, int tl, int tr, int l, int r, int k) { busy(node, tl, tr); if(l<=tl && tr<=r) { lazy[node]=k; busy(node, tl, tr); return; } if(r<tl || tr<l) { return; } int mid=tl+tr>>1; update(node*2, tl, mid, l, r, k); update(node*2+1, mid+1, tr, l, r, k); tree[node]=(tree[node*2]+tree[node*2+1])%MOD; } ll query() { busy(1, 0, N-1); return tree[1]; } }seg; bool solve() { ll t=seg.query(); for(auto it : V) { if(t==it) return true; } return false; } int main() { scanf("%d", &N); ppow[0]=1; for(int i=1; i<=N; i++) { ppow[i]=ppow[i-1]*4%MOD; } for(int i=0; i<3; i++) { A[i]=read(); } for(int i=0; i<3; i++) for(int j=0; j<3; j++) { int k=7-i-j; k%=3; vector<int> now(N); for(int p=0; p<N; p++) { now[p]+=A[0][p]*i; now[p]+=A[1][p]*j; now[p]+=A[2][p]*k; now[p]%=3; } V.push_back(gethash(now)); } scanf("%d", &Q); B=read(); seg.init(1, 0, N-1, B); printf("%s\n", solve() ? "Yes" : "No"); while(Q--) { int l, r, k; char c; scanf("%d%d %c", &l, &r, &c); l--, r--; if(c=='J') k=1; else if(c=='O') k=2; else if(c=='I') k=3; seg.update(1, 0, N-1, l, r, k); printf("%s\n", solve() ? "Yes" : "No"); } }

Compilation message (stderr)

Main.cpp: In member function 'void SEG::init(int, int, int, std::vector<int>&)':
Main.cpp:53:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In member function 'void SEG::update(int, int, int, int, int, int)':
Main.cpp:88:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid=tl+tr>>1;
      |           ~~^~~
Main.cpp: In function 'std::vector<int> read()':
Main.cpp:19:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |  scanf(" %s", S);
      |  ~~~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:141:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |   scanf("%d%d %c", &l, &r, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:80:15: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   80 |    lazy[node]=k;
      |               ^
Main.cpp:148:13: note: 'k' was declared here
  148 |   int l, r, k; char c;
      |             ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...