oj.uz

Submission #1035574

# Submission time Handle Problem Language Result Execution time Memory
1035574 2024-07-26T12:03:32 Z alexander707070 Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 19516 KB 
#include<bits/stdc++.h>
#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*cnt[a][b])%mod) * ((dp[int(w.size())][d[a]^s][d[b]^t]*power[rest])%mod);
            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 31 ms 1912 KB Output is correct
4 Correct 22 ms 1884 KB Output is correct
5 Correct 9 ms 1368 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 31 ms 1912 KB Output is correct
4 Correct 22 ms 1884 KB Output is correct
5 Correct 9 ms 1368 KB Output is correct
6 Correct 1585 ms 2140 KB Output is correct
7 Correct 462 ms 1528 KB Output is correct
8 Correct 1112 ms 1360 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2064 ms 12636 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 2047 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 253 ms 2896 KB Output is correct
2 Correct 260 ms 2764 KB Output is correct
3 Correct 257 ms 2776 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 2896 KB Output is correct
2 Correct 260 ms 2764 KB Output is correct
3 Correct 257 ms 2776 KB Output is correct
4 Execution timed out 2073 ms 15444 KB Time limit exceeded
5 Halted 0 ms 0 KB -

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 31 ms 1912 KB Output is correct
4 Correct 22 ms 1884 KB Output is correct
5 Correct 9 ms 1368 KB Output is correct
6 Correct 1585 ms 2140 KB Output is correct
7 Correct 462 ms 1528 KB Output is correct
8 Correct 1112 ms 1360 KB Output is correct
9 Correct 253 ms 2896 KB Output is correct
10 Correct 260 ms 2764 KB Output is correct
11 Correct 257 ms 2776 KB Output is correct
12 Execution timed out 2048 ms 19516 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 31 ms 1912 KB Output is correct
4 Correct 22 ms 1884 KB Output is correct
5 Correct 9 ms 1368 KB Output is correct
6 Correct 1585 ms 2140 KB Output is correct
7 Correct 462 ms 1528 KB Output is correct
8 Correct 1112 ms 1360 KB Output is correct
9 Correct 253 ms 2896 KB Output is correct
10 Correct 260 ms 2764 KB Output is correct
11 Correct 257 ms 2776 KB Output is correct
12 Execution timed out 2073 ms 15444 KB Time limit exceeded
13 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 31 ms 1912 KB Output is correct
4 Correct 22 ms 1884 KB Output is correct
5 Correct 9 ms 1368 KB Output is correct
6 Correct 1585 ms 2140 KB Output is correct
7 Correct 462 ms 1528 KB Output is correct
8 Correct 1112 ms 1360 KB Output is correct
9 Execution timed out 2064 ms 12636 KB Time limit exceeded
10 Halted 0 ms 0 KB -