oj.uz

답안 #345671

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
345671 2021-01-07T20:19:11 Z oleh1421 Intergalactic ship (IZhO19_xorsum) C++17
0 / 100
 1533 ms 202220 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define endl '\n'
const int N=1010;
const ll mod=1000000007;
int S[7][7][N][N];
int a[N];
ll pw[N*N];
void solve(){
    pw[0]=1ll;
    for (int i=1;i<N*N;i++){
        pw[i]=(pw[i-1]*2ll)%mod;
    }
    int n;cin>>n;
    for (int i=1;i<=n;i++){
        cin>>a[i];
    }
    int q;cin>>q;
    for (int i=1;i<=q;i++){
        int l,r,x;cin>>l>>r>>x;
        for (int j=0;j<7;j++){
            for (int t=0;t<7;t++){
                if ((x&(1<<j)) && (x&(1<<t))){
                    S[j][t][l][r]++;
                }
            }
        }
    }
    for (int x=0;x<7;x++){
        for (int y=0;y<7;y++){
            for (int i=1;i<=n;++i){
                for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i][j-1];
                for (int j=1;j<=n;j++) S[x][y][i][j]+=S[x][y][i-1][j];
            }
        }
    }
    ll res=0ll;
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            ll mult=i*(n-j+1);
            if (i<j) mult*=2;
            for (int x=0;x<7;x++){
                for (int y=0;y<7;y++){
                    int cnt=S[x][y][j][j]-S[x][y][i-1][j]-S[x][y][j][i-1]+S[x][y][i-1][i-1];
                    int cnt_x=S[x][x][j][j]-S[x][x][i-1][j]-S[x][x][j][i-1]+S[x][x][i-1][i-1];
                    int cnt_y=S[y][y][j][j]-S[y][y][i-1][j]-S[y][y][j][i-1]+S[y][y][i-1][i-1];
                    cnt_x-=cnt;
                    cnt_y-=cnt;
                    int SS=(cnt>0)+(cnt_x>0)+(cnt_y>0);
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
//                    if (i==1 && j==1 && x==0 && y==1){
//                        cout<<"OK "<<mult<<" "<<SS<<endl;
//                    }
                    if (SS>=2){
                        res+=pw[q-2+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x)) && (a[j]&(1<<y))){
//                        cout<<i<<" "<<j<<" "<<x<<" "<<y<<endl;
//                        cout<<mult<<endl;
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x)) && (a[j]&(1<<y))==0 && cnt_y){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y)) && cnt_x){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    } else if ((a[i]&(1<<x))==0 && (a[j]&(1<<y))==0 && cnt){
                        res+=pw[q-SS+x+y]*mult;
                        res%=mod;
                    }
                }
            }
        }
    }
    cout<<res<<endl;
}
int32_t main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt=1;
    while (tt--){
        solve();
    }

    return 0;
}
/*
2
1 3
1
1 2 2

*/

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8940 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Incorrect 10 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8940 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Incorrect 10 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 62 ms 27904 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1533 ms 202220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 15 ms 14316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8940 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Incorrect 10 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8940 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Incorrect 10 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8940 KB Output is correct
2 Correct 9 ms 9452 KB Output is correct
3 Incorrect 10 ms 10476 KB Output isn't correct
4 Halted 0 ms 0 KB -