oj.uz

Submission #173249

# Submission time Handle Problem Language Result Execution time Memory
173249 2020-01-03T16:16:58 Z mosiashvililuka Intergalactic ship (IZhO19_xorsum) C++14
17 / 100
 2000 ms 255012 KB 
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,e,f[1009],i,j,zx,xc,xr[(1<<10)][101],pas,mod=1000000007,sm[(1<<20)][31];
pair <pair <long long, long long>, long long> p[1009];
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a;
    for(i=1; i<=a; i++) cin>>f[i];
    cin>>b;
    for(i=0; i<b; i++){
        cin>>p[i].first.first>>p[i].first.second>>p[i].second;
    }
    if(b<=10){
        for(j=1; j<=a; j++) xr[0][j]=f[j];
        for(i=1; i<(1<<b); i++){
            for(zx=b-1; zx>=0; zx--){
                if((i&(1<<zx))!=0) break;
            }
            for(j=1; j<=a; j++){
                if(p[zx].first.first<=j&&j<=p[zx].first.second){
                    xr[i][j]=(xr[i-(1<<zx)][j]^p[zx].second);
                }else{
                    xr[i][j]=xr[i-(1<<zx)][j];
                }
            }
        }
        for(i=0; i<(1<<b); i++){
            for(j=1; j<=a; j++) xr[i][j]+=xr[i][j-1];
            for(zx=1; zx<=a; zx++){
                for(xc=zx-1; xc>=0; xc--){
                    pas+=(xr[i][xc]-xr[i][zx])*(xr[i][xc]-xr[i][zx]);
                    pas%=mod;
                }
            }
        }
        cout<<pas;
        return 0;
    }
    for(j=1; j<=a; j++) sm[0][j]=f[j];
    for(i=1; i<(1<<b); i++){
        for(zx=b-1; zx>=0; zx--){
            if((i&(1<<zx))!=0) break;
        }
        for(j=1; j<=a; j++){
            if(p[zx].first.first<=j&&j<=p[zx].first.second){
                sm[i][j]=(sm[i-(1<<zx)][j]^p[zx].second);
            }else{
                sm[i][j]=sm[i-(1<<zx)][j];
            }
        }
    }
    for(i=0; i<(1<<b); i++){
        for(j=1; j<=a; j++) sm[i][j]+=sm[i][j-1];
        for(j=1; j<=a; j++){
            pas+=sm[i][j]*sm[i][j]*a;
            pas%=mod;
        }
        zx=0;
        for(j=1; j<=a; j++){
            pas-=sm[i][j]*zx*2%mod;
            pas=pas+mod;
          pas%=mod;
            zx+=sm[i][j];
        }
    }
    cout<<pas;
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 97 ms 1200 KB Output is correct
7 Correct 99 ms 1204 KB Output is correct
8 Correct 100 ms 1216 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 254968 KB Output is correct
2 Correct 1679 ms 254956 KB Output is correct
3 Correct 1675 ms 254968 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1672 ms 254968 KB Output is correct
2 Correct 1679 ms 254956 KB Output is correct
3 Correct 1675 ms 254968 KB Output is correct
4 Incorrect 4 ms 504 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 97 ms 1200 KB Output is correct
7 Correct 99 ms 1204 KB Output is correct
8 Correct 100 ms 1216 KB Output is correct
9 Correct 1672 ms 254968 KB Output is correct
10 Correct 1679 ms 254956 KB Output is correct
11 Correct 1675 ms 254968 KB Output is correct
12 Incorrect 24 ms 1400 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 97 ms 1200 KB Output is correct
7 Correct 99 ms 1204 KB Output is correct
8 Correct 100 ms 1216 KB Output is correct
9 Correct 1672 ms 254968 KB Output is correct
10 Correct 1679 ms 254956 KB Output is correct
11 Correct 1675 ms 254968 KB Output is correct
12 Incorrect 4 ms 504 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 1144 KB Output is correct
4 Correct 3 ms 1148 KB Output is correct
5 Correct 4 ms 1144 KB Output is correct
6 Correct 97 ms 1200 KB Output is correct
7 Correct 99 ms 1204 KB Output is correct
8 Correct 100 ms 1216 KB Output is correct
9 Incorrect 26 ms 2936 KB Output isn't correct
10 Halted 0 ms 0 KB -