oj.uz

답안 #715789

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
715789 2023-03-28T01:03:21 Z cig32 Crossing (JOI21_crossing) C++17
100 / 100
 652 ms 22244 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2e5 + 10;
int MOD;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
string gene(string a, string b) {
  string c;
  for(int i=0; i<a.size(); i++) {
    if(a[i] == b[i]) c += a[i];
    else {
      string t = "JOI";
      for(int j=0; j<3; j++) {
        if(a[i] != t[j] && b[i] != t[j]) c += t[j];
      }
    }
  }
  return c;
}
int random_prime(int l, int r) {
  while(1) {
    int x = rnd(l, r);
    int c = 0;
    for(int i=1; i*i<=x; i++) {
      if(x%i == 0) {
        c+=2;
        if(i*i == x) c--;
      }
    }
    if(c==2) return x;
  }
  return 1226;
}
int pre[MAXN];
int bruh;
int geometric_sequence_sum(int a, int x, int n) {
  // S = ax^0+ax^1+...+ax^(n-1)
  // xS = ax^1+ax^2+...+ax^n
  // (x-1)S = ax^n-a
  // S = a(x^n-1)/(x-1)
  
  int s = a;
  s *= pre[n] - 1;
  s %= MOD;
  s *= bruh;
  s %= MOD;
  return s;
}
int ans, n;
void add_segment(int l, int r, int v) {
  ans += geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
  ans %= MOD;
}
void sub_segment(int l, int r, int v) {
  ans -= geometric_sequence_sum(bm(3, n-r-1), 3, r-l+1) * v;
  ans += (MOD << 1);
  ans %= MOD;
}
void solve(int tc) {
  MOD = random_prime(5e8, 1.25 * 1e9);
  cin >> n;
  pre[0] = 1;
  bruh = inv(2);
  for(int i=1; i<=n; i++) pre[i] = (pre[i-1] * 3) % MOD;
  string s[9];
  cin >> s[0] >> s[1] >> s[2];
  s[3] = gene(s[0], s[1]);
  s[4] = gene(s[0], s[2]);
  s[5] = gene(s[1], s[2]);
  s[6] = gene(s[2], s[3]);
  s[7] = gene(s[1], s[4]);
  s[8] = gene(s[0], s[5]);
  int h[9];
  for(int i=0; i<9; i++) {
    h[i] = 0;
    for(int j=0; j<n; j++) {
      h[i] = (h[i] * 3 + (s[i][j] == 'J' ? 0 : (s[i][j] == 'O' ? 1 : 2))) % MOD;
    }
  }
  int q;
  cin >> q;
  string def;
  cin >> def;
  for(char c: def) ans = (ans * 3 + (c == 'J' ? 0 : (c == 'O' ? 1 : 2))) % MOD;
  bool yes = 0;
  for(int i=0; i<9; i++) yes |= (ans == h[i]);
  cout << (yes ? "Yes\n" : "No\n");
  set<pair<pair<int,int>,int> > ranges;
  for(int i=0; i<def.size(); i++) {
    int j = i;
    while(j+1 < def.size() && def[j+1] == def[i]) j++;
    ranges.insert({{i, j}, (def[i] == 'J' ? 0 : (def[i] == 'O' ? 1 : 2))});
    i = j;
  }
  for(int i=0; i<q; i++) {
    int l, r;
    cin >> l >> r;
    --l, --r;
    char c;
    cin >> c;
    auto it = ranges.lower_bound({{l, 0}, 0});
    if(it != ranges.begin()) it--;
    vector<pair<pair<int,int>,int> > to_add, to_sub;
    to_add.push_back({{l, r}, (c == 'J' ? 0 : (c == 'O' ? 1 : 2))});
    while(it != ranges.end() && (*it).first.first <= r) {
      if((*it).first.second >= l) { // relevant
        to_sub.push_back(*it);
        if((*it).first.first < l) {
          to_add.push_back({{(*it).first.first, l-1}, (*it).second});
        }
        if((*it).first.second > r) {
          to_add.push_back({{r+1, (*it).first.second}, (*it).second});
        }
      }
      it++;
    }
    for(auto x: to_sub) {
      ranges.erase(x);
      sub_segment(x.first.first, x.first.second, x.second);
    }
    for(auto x: to_add) {
      ranges.insert(x);
      add_segment(x.first.first, x.first.second, x.second);
    }
    bool yes = 0;
    for(int i=0; i<9; i++) {
      if(h[i] == ans) yes = 1;
    }
    cout << (yes ? "Yes\n" : "No\n");
  }

}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

Compilation message

Main.cpp: In function 'std::string gene(std::string, std::string)':
Main.cpp:25:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(int i=0; i<a.size(); i++) {
      |                ~^~~~~~~~~
Main.cpp: In function 'void solve(long long int)':
Main.cpp:105:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |   for(int i=0; i<def.size(); i++) {
      |                ~^~~~~~~~~~~
Main.cpp:107:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     while(j+1 < def.size() && def[j+1] == def[i]) j++;
      |           ~~~~^~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 1008 KB Output is correct
2 Correct 220 ms 1020 KB Output is correct
3 Correct 161 ms 996 KB Output is correct
4 Correct 193 ms 1040 KB Output is correct
5 Correct 193 ms 1180 KB Output is correct
6 Correct 196 ms 1184 KB Output is correct
7 Correct 195 ms 1224 KB Output is correct
8 Correct 195 ms 1172 KB Output is correct
9 Correct 204 ms 1112 KB Output is correct
10 Correct 206 ms 1132 KB Output is correct
11 Correct 210 ms 1196 KB Output is correct
12 Correct 195 ms 1096 KB Output is correct
13 Correct 243 ms 1132 KB Output is correct
14 Correct 197 ms 1128 KB Output is correct
15 Correct 208 ms 1132 KB Output is correct
16 Correct 210 ms 1100 KB Output is correct
17 Correct 227 ms 1164 KB Output is correct
18 Correct 142 ms 1124 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 1008 KB Output is correct
2 Correct 220 ms 1020 KB Output is correct
3 Correct 161 ms 996 KB Output is correct
4 Correct 193 ms 1040 KB Output is correct
5 Correct 193 ms 1180 KB Output is correct
6 Correct 196 ms 1184 KB Output is correct
7 Correct 195 ms 1224 KB Output is correct
8 Correct 195 ms 1172 KB Output is correct
9 Correct 204 ms 1112 KB Output is correct
10 Correct 206 ms 1132 KB Output is correct
11 Correct 210 ms 1196 KB Output is correct
12 Correct 195 ms 1096 KB Output is correct
13 Correct 243 ms 1132 KB Output is correct
14 Correct 197 ms 1128 KB Output is correct
15 Correct 208 ms 1132 KB Output is correct
16 Correct 210 ms 1100 KB Output is correct
17 Correct 227 ms 1164 KB Output is correct
18 Correct 142 ms 1124 KB Output is correct
19 Correct 516 ms 13288 KB Output is correct
20 Correct 459 ms 15552 KB Output is correct
21 Correct 537 ms 18064 KB Output is correct
22 Correct 533 ms 17208 KB Output is correct
23 Correct 357 ms 2188 KB Output is correct
24 Correct 360 ms 2196 KB Output is correct
25 Correct 597 ms 22244 KB Output is correct
26 Correct 606 ms 18696 KB Output is correct
27 Correct 405 ms 5372 KB Output is correct
28 Correct 464 ms 5368 KB Output is correct
29 Correct 428 ms 5308 KB Output is correct
30 Correct 326 ms 1684 KB Output is correct
31 Correct 420 ms 5436 KB Output is correct
32 Correct 429 ms 5732 KB Output is correct
33 Correct 345 ms 2092 KB Output is correct
34 Correct 545 ms 18812 KB Output is correct
35 Correct 588 ms 15636 KB Output is correct
36 Correct 347 ms 2192 KB Output is correct
37 Correct 338 ms 2084 KB Output is correct
38 Correct 377 ms 15568 KB Output is correct
39 Correct 393 ms 13016 KB Output is correct
40 Correct 577 ms 14392 KB Output is correct
41 Correct 476 ms 18596 KB Output is correct
42 Correct 180 ms 18668 KB Output is correct

Subtask #3
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 1008 KB Output is correct
2 Correct 220 ms 1020 KB Output is correct
3 Correct 161 ms 996 KB Output is correct
4 Correct 193 ms 1040 KB Output is correct
5 Correct 193 ms 1180 KB Output is correct
6 Correct 196 ms 1184 KB Output is correct
7 Correct 195 ms 1224 KB Output is correct
8 Correct 195 ms 1172 KB Output is correct
9 Correct 204 ms 1112 KB Output is correct
10 Correct 206 ms 1132 KB Output is correct
11 Correct 210 ms 1196 KB Output is correct
12 Correct 195 ms 1096 KB Output is correct
13 Correct 243 ms 1132 KB Output is correct
14 Correct 197 ms 1128 KB Output is correct
15 Correct 208 ms 1132 KB Output is correct
16 Correct 210 ms 1100 KB Output is correct
17 Correct 227 ms 1164 KB Output is correct
18 Correct 142 ms 1124 KB Output is correct
19 Correct 213 ms 1044 KB Output is correct
20 Correct 160 ms 1104 KB Output is correct
21 Correct 214 ms 1192 KB Output is correct
22 Correct 168 ms 968 KB Output is correct
23 Correct 204 ms 1108 KB Output is correct
24 Correct 211 ms 996 KB Output is correct
25 Correct 198 ms 1108 KB Output is correct
26 Correct 184 ms 984 KB Output is correct
27 Correct 191 ms 1136 KB Output is correct
28 Correct 177 ms 1048 KB Output is correct
29 Correct 193 ms 1024 KB Output is correct
30 Correct 180 ms 972 KB Output is correct
31 Correct 196 ms 1008 KB Output is correct
32 Correct 191 ms 1104 KB Output is correct
33 Correct 199 ms 1008 KB Output is correct
34 Correct 173 ms 1092 KB Output is correct
35 Correct 200 ms 1096 KB Output is correct
36 Correct 196 ms 1040 KB Output is correct
37 Correct 197 ms 1072 KB Output is correct
38 Correct 226 ms 1048 KB Output is correct
39 Correct 192 ms 1044 KB Output is correct
40 Correct 213 ms 1120 KB Output is correct
41 Correct 200 ms 1100 KB Output is correct
42 Correct 196 ms 1076 KB Output is correct
43 Correct 189 ms 1108 KB Output is correct
44 Correct 196 ms 1000 KB Output is correct

Subtask #4
51.0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 202 ms 1008 KB Output is correct
2 Correct 220 ms 1020 KB Output is correct
3 Correct 161 ms 996 KB Output is correct
4 Correct 193 ms 1040 KB Output is correct
5 Correct 193 ms 1180 KB Output is correct
6 Correct 196 ms 1184 KB Output is correct
7 Correct 195 ms 1224 KB Output is correct
8 Correct 195 ms 1172 KB Output is correct
9 Correct 204 ms 1112 KB Output is correct
10 Correct 206 ms 1132 KB Output is correct
11 Correct 210 ms 1196 KB Output is correct
12 Correct 195 ms 1096 KB Output is correct
13 Correct 243 ms 1132 KB Output is correct
14 Correct 197 ms 1128 KB Output is correct
15 Correct 208 ms 1132 KB Output is correct
16 Correct 210 ms 1100 KB Output is correct
17 Correct 227 ms 1164 KB Output is correct
18 Correct 142 ms 1124 KB Output is correct
19 Correct 516 ms 13288 KB Output is correct
20 Correct 459 ms 15552 KB Output is correct
21 Correct 537 ms 18064 KB Output is correct
22 Correct 533 ms 17208 KB Output is correct
23 Correct 357 ms 2188 KB Output is correct
24 Correct 360 ms 2196 KB Output is correct
25 Correct 597 ms 22244 KB Output is correct
26 Correct 606 ms 18696 KB Output is correct
27 Correct 405 ms 5372 KB Output is correct
28 Correct 464 ms 5368 KB Output is correct
29 Correct 428 ms 5308 KB Output is correct
30 Correct 326 ms 1684 KB Output is correct
31 Correct 420 ms 5436 KB Output is correct
32 Correct 429 ms 5732 KB Output is correct
33 Correct 345 ms 2092 KB Output is correct
34 Correct 545 ms 18812 KB Output is correct
35 Correct 588 ms 15636 KB Output is correct
36 Correct 347 ms 2192 KB Output is correct
37 Correct 338 ms 2084 KB Output is correct
38 Correct 377 ms 15568 KB Output is correct
39 Correct 393 ms 13016 KB Output is correct
40 Correct 577 ms 14392 KB Output is correct
41 Correct 476 ms 18596 KB Output is correct
42 Correct 180 ms 18668 KB Output is correct
43 Correct 213 ms 1044 KB Output is correct
44 Correct 160 ms 1104 KB Output is correct
45 Correct 214 ms 1192 KB Output is correct
46 Correct 168 ms 968 KB Output is correct
47 Correct 204 ms 1108 KB Output is correct
48 Correct 211 ms 996 KB Output is correct
49 Correct 198 ms 1108 KB Output is correct
50 Correct 184 ms 984 KB Output is correct
51 Correct 191 ms 1136 KB Output is correct
52 Correct 177 ms 1048 KB Output is correct
53 Correct 193 ms 1024 KB Output is correct
54 Correct 180 ms 972 KB Output is correct
55 Correct 196 ms 1008 KB Output is correct
56 Correct 191 ms 1104 KB Output is correct
57 Correct 199 ms 1008 KB Output is correct
58 Correct 173 ms 1092 KB Output is correct
59 Correct 200 ms 1096 KB Output is correct
60 Correct 196 ms 1040 KB Output is correct
61 Correct 197 ms 1072 KB Output is correct
62 Correct 226 ms 1048 KB Output is correct
63 Correct 192 ms 1044 KB Output is correct
64 Correct 213 ms 1120 KB Output is correct
65 Correct 200 ms 1100 KB Output is correct
66 Correct 196 ms 1076 KB Output is correct
67 Correct 189 ms 1108 KB Output is correct
68 Correct 196 ms 1000 KB Output is correct
69 Correct 450 ms 12140 KB Output is correct
70 Correct 515 ms 15556 KB Output is correct
71 Correct 356 ms 2060 KB Output is correct
72 Correct 354 ms 2064 KB Output is correct
73 Correct 380 ms 2136 KB Output is correct
74 Correct 563 ms 16380 KB Output is correct
75 Correct 403 ms 2040 KB Output is correct
76 Correct 618 ms 21980 KB Output is correct
77 Correct 592 ms 13712 KB Output is correct
78 Correct 375 ms 2068 KB Output is correct
79 Correct 388 ms 2108 KB Output is correct
80 Correct 539 ms 14380 KB Output is correct
81 Correct 375 ms 2144 KB Output is correct
82 Correct 652 ms 21984 KB Output is correct
83 Correct 622 ms 17580 KB Output is correct
84 Correct 383 ms 2108 KB Output is correct
85 Correct 382 ms 2052 KB Output is correct
86 Correct 571 ms 12784 KB Output is correct
87 Correct 470 ms 5472 KB Output is correct
88 Correct 345 ms 1892 KB Output is correct
89 Correct 450 ms 5908 KB Output is correct
90 Correct 599 ms 7104 KB Output is correct
91 Correct 360 ms 1616 KB Output is correct
92 Correct 567 ms 15508 KB Output is correct
93 Correct 363 ms 2092 KB Output is correct
94 Correct 372 ms 2096 KB Output is correct
95 Correct 398 ms 2068 KB Output is correct
96 Correct 331 ms 5116 KB Output is correct
97 Correct 395 ms 13000 KB Output is correct
98 Correct 612 ms 14156 KB Output is correct
99 Correct 556 ms 18716 KB Output is correct
100 Correct 181 ms 18684 KB Output is correct