QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#825486#9774. Same Sumucup-team3691#TL 3ms104968kbC++145.8kb2024-12-21 19:44:122024-12-21 19:44:13

Judging History

你现在查看的是最新测评结果

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2024-12-23 17:02:06]
  • hack成功,自动添加数据
  • (/hack/1310)
  • [2024-12-23 16:48:26]
  • hack成功,自动添加数据
  • (/hack/1309)
  • [2024-12-23 16:33:45]
  • hack成功,自动添加数据
  • (/hack/1308)
  • [2024-12-23 16:23:53]
  • hack成功,自动添加数据
  • (/hack/1307)
  • [2024-12-23 16:13:08]
  • hack成功,自动添加数据
  • (/hack/1306)
  • [2024-12-23 15:54:42]
  • hack成功,自动添加数据
  • (/hack/1305)
  • [2024-12-23 14:58:39]
  • hack成功,自动添加数据
  • (/hack/1304)
  • [2024-12-23 09:58:11]
  • hack成功,自动添加数据
  • (/hack/1302)
  • [2024-12-23 09:47:22]
  • hack成功,自动添加数据
  • (/hack/1301)
  • [2024-12-23 09:41:23]
  • hack成功,自动添加数据
  • (/hack/1300)
  • [2024-12-23 09:26:32]
  • hack成功,自动添加数据
  • (/hack/1299)
  • [2024-12-23 09:19:58]
  • hack成功,自动添加数据
  • (/hack/1298)
  • [2024-12-23 09:13:29]
  • hack成功,自动添加数据
  • (/hack/1297)
  • [2024-12-22 18:52:18]
  • hack成功,自动添加数据
  • (/hack/1296)
  • [2024-12-22 18:13:14]
  • hack成功,自动添加数据
  • (/hack/1294)
  • [2024-12-21 19:44:13]
  • 评测
  • 测评结果:TL
  • 用时:3ms
  • 内存:104968kb
  • [2024-12-21 19:44:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

const int DIM = 2e5 + 5;
const int P = 6;

const int H1 = 1e9 + 7;
const int H2 = 998244353;

struct myhash {
  myhash() : h1(0), h2(0) {}
  myhash(ll x) : h1((x % H1) + H1), h2((x % H2) + H2) {
    if (h1 >= H1)
      h1 -= H1;

    if (h2 >= H2)
      h2 -= H2;
  }

  bool operator != (const myhash &oth) const {
    return (oth.h1 != h1) || (oth.h2 != h2);
  }

  myhash& operator += (myhash rhs) {
    h1 = (h1 + rhs.h1);
    if (h1 >= H1)
      h1 -= H1;

    h2 = (h2 + rhs.h2);
    if (h2 >= H2)
      h2 -= H2;

    return *this;
  }

  myhash operator + (myhash rhs) {
    myhash x;
    x.h1 = (h1 + rhs.h1);
    if (x.h1 >= H1)
      x.h1 -= H1;

    x.h2 = (h2 + rhs.h2);
    if (x.h2 >= H2)
      x.h2 -= H2;

    return x;
  }

  myhash operator * (myhash rhs) {
    myhash x;
    x.h1 = 1LL * h1 * rhs.h1 % H1;
    x.h2 = 1LL * h2 * rhs.h2 % H2;

    return x;
  }

  int h1, h2;
};

struct sums {
  myhash s[P + 1];
};

struct node {
  ll mx, mn;
  sums s, sn;
};

int n, k, q;
int a[DIM];

ll c[P + 1][P + 1];
ll lazy[4 * DIM];

node arb[4 * DIM];

void init() {
  c[0][0] = 1;
  for (int i = 1; i <= P; ++i) {
    c[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    }
  }
}

void comb(sums &x, sums &y, sums &z) {
  for (int i = 0; i <= P; ++i) {
    x.s[i] = y.s[i] + z.s[i];
  }
}

void comb(node &x, node &y, node &z) {
  comb(x.sn, y.sn, z.sn);
  comb(x.s, y.s, z.s);
  x.mx = max(y.mx, z.mx);
  x.mn = min(y.mn, z.mn);
}

void recalc(sums &x, ll v) {
  for (int i = P; i >= 1; --i) {
    myhash val(1);
    for (int j = 1; j <= i; ++j) {
      val = val * myhash(v);
      x.s[i] += x.s[i - j] * val * myhash(c[i][j]);
    }
  }
}

void recalc(node &x, ll v) {
  recalc(x.s, v);
  recalc(x.sn, -v);

  x.mn += v;
  x.mx += v;
}

void propag(int nod) {
  if (!lazy[nod]) {
    return;
  }

  for (int i = nod * 2; i <= nod * 2 + 1; ++i) {
    lazy[i] += lazy[nod];
    recalc(arb[i], lazy[nod]);
  }

  lazy[nod] = 0;
}

void build(int st = 1, int dr = n, int nod = 1) {
  if (st == dr) {
    myhash x = 1, xn = 1;
    for (int i = 1; i <= P; ++i) {
      x = x * a[st];
      xn = xn * -(a[st]);
      arb[nod].s.s[i] = x;
      arb[nod].sn.s[i] = xn; 
    }
    arb[nod].s.s[0] = arb[nod].sn.s[0] = 1; 
    arb[nod].mn = arb[nod].mx = a[st];
    return;
  }

  int mij = (st + dr) / 2;
  build(st, mij, nod * 2);
  build(mij + 1, dr, nod * 2 + 1);

  comb(arb[nod], arb[nod * 2], arb[nod * 2 + 1]);
}

void update(int x, int y, int v, int st = 1, int dr = n, int nod = 1) {
  if (x <= st && dr <= y) {
    lazy[nod] += v;
    recalc(arb[nod], v);
    return;
  }

  propag(nod);

  int mij = (st + dr) / 2;
  if (x <= mij) {
    update(x, y, v, st, mij, nod * 2);
  }
  if (mij + 1 <= y){
    update(x, y, v, mij + 1, dr, nod * 2 + 1);
  }

  comb(arb[nod], arb[nod * 2], arb[nod * 2 + 1]);
}

node query(int x, int y, int st = 1, int dr = n, int nod = 1) {
  if (x <= st && dr <= y) {
    return arb[nod];
  }

  propag(nod);
  int mij = (st + dr) / 2;
  if (x <= mij && mij + 1 <= y) {
    node ans;
    node l = query(x, y, st, mij, nod * 2); 
    node r = query(x, y, mij + 1, dr, nod * 2 + 1);
    comb(ans, l, r);
    return ans;
  }

  if (x <= mij) {
    return query(x, y, st, mij, nod * 2);
  }
  
  return query(x, y, mij + 1, dr, nod * 2 + 1);
}

void solve() {
  init();

  cin >> n >> q;
  int g = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    a[i] += g;
  }

  build();

  for (int i = 1; i <= q; ++i) {
    int t, x, y, v;
    cin >> t >> x >> y;

    if (t == 1) {
      cin >> v;
      update(x, y, v);
    } else {
      node g = query(x, y);
      update(x, y, -g.mx - g.mn);
      node h = query(x, y);
      update(x, y, g.mx + g.mn);

//      for (int i = 0; i <= P; ++i) {
//        cout << "(" << g.s.s[i].h1 << ", " << g.s.s[i].h2 << ")" << " ";
//      }
//      cout << "\n";
//
//      for (int i = 0; i <= P; ++i) {
//        cout << "(" << h.sn.s[i].h1 << ", " << h.sn.s[i].h2 << ")" << " ";
//      }
//      cout << "\n";

      bool ok = true;
      for (int i = 1; i <= P; ++i) {
        if (g.s.s[i] != h.sn.s[i]) {
          ok = false;
          break;
        }
      }

      cout << (ok ? "YES" : "NO") << "\n";
    }
  }
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
//  cin >> t;
  while (t--)
    solve();

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 104968kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100
Time Limit Exceeded

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result: