QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#655112#6435. Paimon Segment TreellleiCompile Error//C++203.9kb2024-10-19 00:38:182024-10-19 00:38:19

Judging History

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

  • [2024-10-19 00:38:19]
  • 评测
查看
  • [2024-10-19 00:38:18]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 5e4 + 5;
int n, m, q;
int a[N];
struct Matrix {
    int mt[4][4];
    Matrix() : mt{} {}
    Matrix(int b) : mt{} {
        mt[0][0] = 1;
        mt[0][1] = b % mod, mt[1][1] = 1;
        mt[0][2] = b * 1ll * b % mod, mt[1][2] = 2 * 1ll * b % mod, mt[2][2] = 1;
        mt[0][3] = mt[0][2], mt[1][3] = mt[1][2], mt[2][3] = mt[3][3] = 1;
    }
} E;
int md(int x) { return x >= mod ? x - mod : x; }
Matrix operator*(const Matrix &a, const Matrix &b) {
    Matrix c;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            for (int k = 0; k < 4; k++)
                c.mt[i][j] = md(a.mt[i][k] * 1LL * b.mt[k][j] % mod + c.mt[i][j]);
        }
    return c;
}
Matrix operator+(const Matrix &a, const Matrix &b) {
    Matrix c;
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++) {
            c.mt[i][j] = md(a.mt[i][j] + b.mt[i][j]);
        }
    return c;
}
Matrix tag[N << 2];
Matrix sum[N << 2];
int vis[N << 2];
void pushdown(int rt) {
    if (vis[rt]) {
        sum[rt << 1] = sum[rt << 1] * tag[rt];
        sum[rt << 1 | 1] = sum[rt << 1 | 1] * tag[rt];
        tag[rt << 1] = tag[rt << 1] * tag[rt];
        tag[rt << 1 | 1] = tag[rt << 1 | 1] * tag[rt];
        vis[rt << 1] = 1;
        vis[rt << 1 | 1] = 1;
        tag[rt] = E;
        vis[rt] = 0;
    }
}
void update(int L, int R, int l, int r, int rt, int b) {
    if (L <= l && r <= R) {
        Matrix tmp = Matrix(b);
        tag[rt] = tag[rt] * tmp;
        sum[rt] = sum[rt] * tmp;
        vis[rt] = 1;
        return;
    }
    pushdown(rt);
    int mid = l + r >> 1;
    if (L <= mid)
        update(L, R, l, mid, rt << 1, b);
    if (R > mid)
        update(L, R, mid + 1, r, rt << 1 | 1, b);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
int query(int L, int R, int l, int r, int rt) {
    if (L <= l && r <= R)
        return sum[rt].mt[0][3];
    pushdown(rt);
    int mid = l + r >> 1, ans = 0;
    if (L <= mid)
        ans = (ans + query(L, R, l, mid, rt << 1)) % mod;
    if (R > mid)
        ans = (ans + query(L, R, mid + 1, r, rt << 1 | 1)) % mod;
    return ans;
}
void build(int l, int r, int rt) {
    tag[rt] = E;
    if (l == r) {
        sum[rt] = E;
        return;
    }
    int mid = l + r >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
int L[N], R[N], W[N];
int ans[N];
vector<pair<pair<int, int>, pair<int, int>>> qr[N];
int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> n >> m >> q;
    for (int i = 0; i < 4; i++)
        E.mt[i][i] = 1;
    build(1, n, 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        update(i, i, 1, n, 1, x);
    }
    for (int i = 1; i <= m; i++)
        cin >> L[i] >> R[i] >> W[i];
    for (int i = 1; i <= q; i++) {
        int l, r, x, y;
        cin >> l >> r >> x >> y;
        if (x >= 1)
            qr[x - 1].push_back({{l, r}, {i, -1}});
        qr[y].push_back({{l, r}, {i, 1}});
    }
    for (int i = 0; i <= m; i++) {

        if (i) {
            if (L[i] - 1 >= 1)
                update(1, L[i] - 1, 1, n, 1, 0);
            update(L[i], R[i], 1, n, 1, W[i]);
            if (R[i] + 1 <= n)
                update(R[i] + 1, n, 1, n, 1, 0);
        }
        for (auto t : qr[i]) {
            int l = t.first.first;
            int r = t.first.second;
            // cout << query(l, r, 1, n, 1) << ' ' << i << '%' << '\n';
            ans[t.second.first] += query(l, r, 1, n, 1) * t.second.second;
            ans[t.second.first] %= mod;
        }
    }
    for (int i = 1; i <= q; i++)
        cout << (ans[i] % mod + mod) % mod << '\n';
}
Source code, Language: C++20

Details 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

Server Time: 2024-12-04 23:01:06 | OpenSource Project