oj.uz

Submission #1035641

# Submission time Handle Problem Language Result Execution time Memory
1035641 2024-07-26T12:46:40 Z alexander707070 Intergalactic ship (IZhO19_xorsum) C++14
28 / 100
 2000 ms 20048 KB 
#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#define MAXN 100007
using namespace std;
 
struct query{
    int type,val;
};
 
const int maxa=128;
const long long mod=1e9+7;
 
int n,d[MAXN],q,l[MAXN],r[MAXN],x[MAXN];
 
long long dp[507][150][150];
long long power[100007];
long long cnt[1007][1007],ans;
 
vector<query> w;
int li[207][3],tim,rest;
int br[207][3];
 
void calcdp(){
    dp[0][0][0]=1;
 
    for(int pos=1;pos<=int(w.size());pos++){
        for(int s=0;s<maxa;s++){
            for(int t=0;t<maxa;t++){
 
                if(w[pos-1].type==0){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s^w[pos-1].val][t])*power[br[w[pos-1].val][0]-1];
                }
 
                if(w[pos-1].type==1){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s][t^w[pos-1].val])*power[br[w[pos-1].val][1]-1];
                }
 
                if(w[pos-1].type==2){
                    dp[pos][s][t]=(dp[pos-1][s][t] + dp[pos-1][s^w[pos-1].val][t^w[pos-1].val])*power[br[w[pos-1].val][2]-1];
                }
 
                dp[pos][s][t]%=mod;
            }
        }
    }
}
 
bool in(int a,int l,int r){
    return a>=l and a<=r;
}
 
long long calc(int a,int b){
    long long res=0;
 
    rest=0; tim++;
    w.clear();
 
    for(int i=0;i<=200;i++){
        for(int f=0;f<3;f++)br[i][f]=0;
    }
 
    for(int i=1;i<=q;i++){
        if(!in(a,l[i],r[i]) and !in(b,l[i],r[i]))rest++;
 
        if(in(a,l[i],r[i]) and !in(b,l[i],r[i])){
            if(li[x[i]][0]!=tim)w.push_back({0,x[i]});
            li[x[i]][0]=tim;
            br[x[i]][0]++;
        }
        if(!in(a,l[i],r[i]) and in(b,l[i],r[i])){
            if(li[x[i]][1]!=tim)w.push_back({1,x[i]});
            li[x[i]][1]=tim;
            br[x[i]][1]++;
        }
        if(in(a,l[i],r[i]) and in(b,l[i],r[i])){
            if(li[x[i]][2]!=tim)w.push_back({2,x[i]});
            li[x[i]][2]=tim;
            br[x[i]][2]++;
        }
    }
 
    calcdp();
 
    for(long long s=0;s<maxa;s++){
        for(long long t=0;t<maxa;t++){
            res+=(s*t*dp[int(w.size())][d[a]^s][d[b]^t])%mod;
            res%=mod;
        }
    }

    res*=power[rest];
    res%=mod;

    res*=cnt[a][b];
    res%=mod;
 
    return res;
}
 
int main(){
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
 
    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            cnt[i][f]=i*(n-f+1);
            if(i!=f)cnt[i][f]*=2;
        }
    }
 
    cin>>q;
    for(int i=1;i<=q;i++){
        cin>>l[i]>>r[i]>>x[i];
    }
 
    power[0]=1;
    for(int i=1;i<=q;i++){
        power[i]=(power[i-1]*2)%mod;
    }
 
    for(int i=1;i<=n;i++){
        for(int f=i;f<=n;f++){
            ans+=calc(i,f);
            ans%=mod;
        }
    }
 
    cout<<ans<<"\n";
 
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 16 ms 1920 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 16 ms 1920 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 1091 ms 2140 KB Output is correct
7 Correct 377 ms 1360 KB Output is correct
8 Correct 762 ms 1364 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 13400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 7516 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 2716 KB Output is correct
2 Correct 175 ms 2896 KB Output is correct
3 Correct 169 ms 2880 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 2716 KB Output is correct
2 Correct 175 ms 2896 KB Output is correct
3 Correct 169 ms 2880 KB Output is correct
4 Correct 1401 ms 15444 KB Output is correct
5 Correct 1348 ms 15536 KB Output is correct
6 Correct 1331 ms 15536 KB Output is correct
7 Correct 1312 ms 15440 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 16 ms 1920 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 1091 ms 2140 KB Output is correct
7 Correct 377 ms 1360 KB Output is correct
8 Correct 762 ms 1364 KB Output is correct
9 Correct 158 ms 2716 KB Output is correct
10 Correct 175 ms 2896 KB Output is correct
11 Correct 169 ms 2880 KB Output is correct
12 Execution timed out 2105 ms 20048 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 16 ms 1920 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 1091 ms 2140 KB Output is correct
7 Correct 377 ms 1360 KB Output is correct
8 Correct 762 ms 1364 KB Output is correct
9 Correct 158 ms 2716 KB Output is correct
10 Correct 175 ms 2896 KB Output is correct
11 Correct 169 ms 2880 KB Output is correct
12 Correct 1401 ms 15444 KB Output is correct
13 Correct 1348 ms 15536 KB Output is correct
14 Correct 1331 ms 15536 KB Output is correct
15 Correct 1312 ms 15440 KB Output is correct
16 Execution timed out 2105 ms 20048 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 1920 KB Output is correct
4 Correct 16 ms 1920 KB Output is correct
5 Correct 7 ms 1372 KB Output is correct
6 Correct 1091 ms 2140 KB Output is correct
7 Correct 377 ms 1360 KB Output is correct
8 Correct 762 ms 1364 KB Output is correct
9 Execution timed out 2012 ms 13400 KB Time limit exceeded
10 Halted 0 ms 0 KB -