QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#314646#7782. Ursa MinorDelay_for_five_minutesWA 0ms24264kbC++205.9kb2024-01-26 01:55:092024-01-26 01:55:10

Judging History

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

  • [2024-01-26 01:55:10]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:24264kb
  • [2024-01-26 01:55:09]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n , m , q;
const int bs = 7797;
const int mod = (1<<31)-1;
int a[200005] ;
int st[20][200005];
int qry(int l,int r) {
    int k = __lg(r - l + 1) ;
    return __gcd(st[k][l] , st[k][r - (1<<k) + 1]) ;
}
int pw[200005] , prep[200005];
struct ST1 {
    int pr[505] ; //前缀和
    int block[200005]; // 所属块
    int pre[505][505] ;///每块前缀和
    int L[505] , R[505];
    int a[200005];
    int B;
    void init() {
        for(int i = 1;i <= n;i++) {
            block[i] = block[i - 1];
            if(B == 1 || i % B == 1) {
                block[i]++ ;
                R[block[i - 1]] = i - 1;
                L[block[i]] = i;
            }
        }
        R[block[n]] = n ;
        for(int i = 1;i <= block[n];i++) {
            for(int j = L[i] ; j <= R[i] ;j++) {
                pre[i][j - L[i] + 1] = (pre[i][j - L[i]] + a[j]) % mod;
            }
            pr[i] = (pr[i - 1] + pre[i][R[i] - L[i] + 1]) % mod;
        }
    }
    void upd(int pos,int v) {
        a[pos] = v;
        int i = block[pos] ;
        for(int j = pos ; j <= R[i] ;j++) {
            pre[i][j - L[i] + 1] = (pre[i][j - L[i]] + a[j]) % mod;
        }
        for(int j = i ; j <= block[n];j++) pr[j] = (pr[j - 1] + pre[j][R[j] - L[j] + 1]) % mod;
    }
    int qry(int l,int r) {
        int bl = block[l] , br = block[r] ;
        if(bl == br) {
            return (pre[bl][r - L[bl] + 1] - pre[bl][l - L[bl]] + mod ) % mod;
        }
        return ((pre[br][r - L[br] + 1] - pre[bl][l - L[bl]]
        + pr[br - 1] - pr[bl - 1])%mod + mod ) % mod;
    }
}s1;

struct ST2 {
    int a[200005];
    int pr[505];
    int B;
    void init() {
        int cnt = 0;
        for(int i = 1;i <= n;i++) {
            if(i % B == 1 || B == 1) ++cnt;
            pr[cnt] = (pr[cnt] + a[i]) % mod;
        }
    }
    void upd(int pos,int v) {
        int id = (pos - 1) / B + 1;
        pr[id] = ((ll)pr[id] - a[pos] + v + mod) % mod;
        a[pos] = v;
        return ;
    }
    int qry(int l,int r) {
        int idl = (l - 1) / B + 1 , idr = (r - 1) / B + 1;
        if(idl == idr) {
            int ans = 0;
            for(int j = l;j <= r;j++) ans = (ans + a[j]) % mod;
            return ans;
        }
        int ans = 0;
        if(l > idl * B - B/2) {
            for(int j = l;j <= idl*B;j++) ans = (ans + a[j]) % mod;
        }
        else {
            ans = (ans + pr[idl]) % mod;
            for(int j = (idl-1)*B + 1 ; j < l;j++) ans = (ans - a[j]) % mod;
            ans = (ans + mod) % mod;
        }
        if(r > idr*B - B/2) {
            ans = (ans + pr[idr]) % mod;
            for(int j = r + 1;j <= idr*B;j++) ans = (ans - a[j]) % mod;
            ans = (ans + mod) % mod;
        }
        else{
            for(int j = (idr-1)*B + 1 ; j <= r;j++) ans = (ans + a[j]) % mod;
        }
        for(int j = idl + 1;  j <= idr - 1;j++) ans = (ans + pr[j]) % mod;
        return ans;
    }
}S[450];
void solv()
{
    cin >> n >> m >> q;
    pw[0] = 1; prep[0] = 1;
    for(int i = 1;i <= n;i++) {pw[i] = 1LL * pw[i - 1] * bs % mod; prep[i] = (prep[i - 1] + pw[i]) % mod;}
    for(int i = 1;i <= n;i++) {cin >> a[i] ;}
    for(int i = 1;i <= m;i++) {
        cin >> st[0][i] ;
    }
    for(int i = 1;i <= 19;i++) {
        for(int j = 1;j <= m;j++) {
            if(j + (1 << i - 1) <= m) st[i][j] = __gcd(st[i - 1][j] , st[i - 1][j + (1 << i - 1)]) ;
            else st[i][j] = st[i - 1][j] ;
        }
    }
    s1.B = sqrt(n) ;
    int B = sqrt(n) ;
    for(int i = 1;i <= n;i++) s1.a[i] = 1LL * pw[n - i] * a[i] % mod;
    s1.init() ;

    for(int k = 1;k <= B;k++) {
        S[k].B = sqrt(n);
        for(int i = 1;i <= n;i++) {
            S[k].a[i] = 1LL * a[i] * pw[i % k] % mod;
            if(i % k == 0) S[k].a[i] = (S[k].a[i] - 1LL * a[i] * prep[k - 1]%mod + mod) % mod;
        }
        S[k].init() ;
    }
    // puts("ojbk") ;
    int n0 = 0 , n1 = 0 , n2 = 0;
    for(int x= 1;x <= q;x++){
        char op ; cin >> op ;
        if(op == 'Q') {
            int l , r , s , t;
            cin >> l >> r >> s >> t;
            int k = __gcd(r - l + 1 , qry(s , t)) ;
            if(k > B) {
                n0++;
                int sum = 0;
                int s0 = 0 , ql = l, qr = l + k - 1;
                for(int i = 0 ; i < (r - l + 1) / k ; i++) {
                    sum = (sum + 1LL * s1.qry(ql, qr) * pw[i * k]) % mod; 
                    s0 = (s0 + a[ql]) % mod;
                    ql += k ; qr += k;
                }
                if(l + k <= n) s0 = 1LL * s0 * (prep[n - l] - prep[n - l - k] + mod) % mod;
                else s0 = 1LL * s0 * prep[n - l] % mod;
                    if(s0 == sum) cout << "Yes\n" ;
                    else cout << "No\n" ;
                
            }
            else {
                n1++;
                int sum = S[k].qry(l , r);
                    if(sum == 0) cout << "Yes\n";
                    else cout << "No\n" ;
                
            }
        }
        else {
            n2++;
            int u , v ; cin >> u >> v;
            a[u] = v;
            s1.upd(u , 1LL * a[u] * pw[n - u] % mod) ;

    // puts("ojbk??") ;
            for(int k = 1;k <= B;k++) {
                int val = 1LL * a[u] * pw[u % k] % mod;
                if(u % k == 0) val = (val - 1LL * a[u] * prep[k - 1]%mod + mod) % mod;
                S[k].upd(u , val);
            }
    // puts("ojbk") ;
        }
    }
    return;
}
int main()
{
    // freopen("in.txt","r",stdin) ;
    // freopen("out.txt","w",stdout) ;
    ios::sync_with_stdio(false) ; cin.tie(0) ; cout.tie(0) ;
    int T = 1;
    clock_t st = clock() ;
    while(T--) solv();
    // cerr << (double)(clock()- st) / CLOCKS_PER_SEC << '\n' ;
    return 0;
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 24264kb

input:

6 4 5
1 1 4 5 1 4
3 3 2 4
Q 1 5 1 2
Q 2 5 3 4
U 5 2
Q 1 6 1 2
Q 2 5 3 4

output:

Yes
No
No
No

result:

wrong answer 4th words differ - expected: 'Yes', found: 'No'