fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp> // Common file
  3. #include <ext/pb_ds/tree_policy.hpp> // Including stree_order_statistics_node_update
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. //data structure (fenwick substitute)
  9. template <typename T>
  10. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  11.  
  12. #define pb push_back
  13. #define eb emplace_back
  14. #define mp make_pair
  15. #define pii pair<int, int>
  16. #define vi vector<int>
  17. #define pll pair<ll, ll>
  18. #define fi first
  19. #define se second
  20. #define ull uint64_t
  21. #define ll int64_t
  22.  
  23. //debugging snippets
  24. #define Local freopen("input","r",stdin)
  25. #define tr1(x)                cerr << #x << ": " << x << endl;
  26. #define tr2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  27. #define tr3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  28. #define tr4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  29. struct Node {
  30.     int pre6[5];
  31.     int pre7[5];
  32. };
  33.  
  34. Node stree[800000];
  35. string S;
  36.  
  37. Node merge(const Node & a, const Node & b) {
  38.     Node n;
  39.     for (int i = 0; i < 5; ++i) {
  40.         n.pre6[i] = b.pre6[a.pre6[i]];
  41.         n.pre7[i] = b.pre7[a.pre7[i]];
  42.     }
  43.     return n;
  44. }
  45.  
  46. void build(int nd, int l, int r) {
  47.     if (l == r) {
  48.         Node & n = stree[nd];
  49.         for (int i = 0; i < 4; ++i) {
  50.             n.pre6[i] = i + ("2016"[i] == S[l]);
  51.             n.pre7[i] = i + ("2017"[i] == S[l]);
  52.         }
  53.         n.pre6[4] = n.pre7[4] = 4;
  54.     } else {
  55.         int m = (l + r) / 2;
  56.         build(2 * nd + 1, l, m);
  57.         build(2 * nd + 2, m + 1, r);
  58.         stree[nd] = merge(stree[2 * nd + 1], stree[2 * nd + 2]);
  59.     }
  60. }
  61.  
  62. Node qry(int nd, int l, int r, int ql, int qr) {
  63.     if (l == ql && r == qr) {
  64.         return stree[nd];
  65.     } else {
  66.         int m = (l + r) / 2;
  67.         if (qr <= m) return qry(2 * nd + 1, l, m, ql, qr);
  68.         if (ql > m) return qry(2 * nd + 2, m + 1, r, ql, qr);
  69.         Node q1 = qry(2 * nd + 1, l, m, ql, m);
  70.         Node q2 = qry(2 * nd + 2, m + 1, r, m + 1, qr);
  71.         return merge(q1, q2);
  72.     }
  73. }
  74.  
  75. int main() {
  76.     Local; //local testing
  77.     int n, q;
  78.     cin >> n >> q;
  79.     cin >> S;
  80.     build(0, 0, n - 1);
  81.     for (int i = 1; i <= q; ++i) {
  82.         int a, b;
  83.         string qans;
  84.         cin >> a >> b >> qans;
  85.         a--;
  86.         b--;
  87.         Node r = qry(0, 0, n - 1, a, b);
  88.         string ans;
  89.         if (r.pre7[0] == 4 && r.pre6[0] < 4) ans = "yes";
  90.         else ans = "no";
  91.         string corr = ans == qans ? "correct" : "incorrect";
  92.         cout << ans << " " << qans << " " << corr << '\n';
  93.     }
  94.     return 0;
  95. }
  96.  
Runtime error #stdin #stdout 0s 34720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gvpKLk
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!