oj.uz

Submission #441169

# Submission time Handle Problem Language Result Execution time Memory
441169 2021-07-04T13:10:16 Z leaked Intergalactic ship (IZhO19_xorsum) C++14
100 / 100
 1514 ms 7680 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC opimize(-O3)
//#pragma GCC opimize(Ofast)
//#pragma GCC opimize(unroll-loops)
//#pragma GCC target("avx,avx2,popcnt,sse,sse2,sse3,sse4,abm,tune=native")
#define m_p make_pair
#define vec vector
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int)x.size()
#define pw(x) (1<<x)
#define f first
#define s second

using namespace std;
using namespace __gnu_pbds;
typedef long double ld;
typedef pair<int,int> pii;
const int N=1e3+2;
const int Q=1e5+3;
const int M=1e9+7;
//int pref[4][N][N];
int prec[2][Q];
int p2[Q];
vec<array<int,3>>go[4];
int mult(int a,int b){
    return 1ll*a*b%M;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
struct _2d{
    int pref[N][N];
    void clr(){
        for(int i=0;i<N;i++){
            fill(pref[i],pref[i]+N,0);
        }
    }
    void build(){
        for(int i=0;i<N;i++){
            for(int j=1;j<N;j++){
                pref[i][j]+=pref[i][j-1];
            }
        }
        for(int i=1;i<N;i++){
            for(int j=0;j<N;j++){
                pref[i][j]+=pref[i-1][j];
            }
        }
    }
    int get(int x1,int x2,int y1,int y2){
        if(x1>x2) return 0;
        int w=pref[x2][y2];
        if(x1) w-=pref[x1-1][y2];
        if(y1) w-=pref[x2][y1-1];
        if(x1 && y1) w+=pref[x1-1][y1-1];
        return w;
    }
}st;
struct _1d{
    int pref[N];
    void clr(){
        for(int i=0;i<N;i++) pref[i]=0;
    }
    void build(){
        for(int i=1;i<N;i++){
            pref[i]+=pref[i-1];
        }
    }
    int get(int x){
        return pref[x];
    }
}lol[2];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    p2[0]=1;for(int i=1;i<Q;i++) p2[i]=mult(p2[i-1],2);
    vec<int>a(n);
    for(auto &z : a)
        cin>>z;
    int q;
    cin>>q;
    vec<int>l(q),r(q),x(q);
    for(int i=0;i<q;i++){
        cin>>l[i]>>r[i]>>x[i];--l[i];--r[i];
    }
    for(int i=0;i<4;i++){
        for(int f=0;f<2;f++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    int msk=i;
                    if(f) msk^=1;
                    if(j) msk^=2;
                    if(k) msk^=3;
                    if(msk==3){
                        go[i].pb({f,j,k});
                    }
                }
            }
        }
    }
    prec[0][0]=1;
    for(int i=0;i<=q;i++){
        for(int cr=0;cr<2;cr++){
            add(prec[cr][i+1],prec[cr][i]);
            add(prec[cr^1][i+1],prec[cr][i]);
        }
    }
    int ans=0;
    for(int b1=0;b1<7;b1++){
        for(int b2=0;b2<7;b2++){
            st.clr();
            lol[0].clr();lol[1].clr();
            for(int i=0;i<q;i++){
                if(x[i]&(1<<b1) && x[i]&(1<<b2)) st.pref[l[i]][r[i]]++;
                if(x[i]&(1<<b1)) lol[0].pref[l[i]]++,lol[0].pref[r[i]+1]--;
                if(x[i]&(1<<b2)) lol[1].pref[r[i]+1]--,lol[1].pref[l[i]]++;
            }
            st.build();
            lol[0].build();lol[1].build();
            int s=0;
            for(int i=0;i<n;i++){
                for(int j=i;j<n;j++){
                    int start=((a[i]>>b1)&1)+(((a[j]>>b2)&1)<<1);
                    int x3=st.get(0,i,j,n-1);
                    int x1=lol[0].pref[i]-x3;
                    int x2=lol[1].pref[j]-x3;
                    int x0=q-x1-x2-x3;
                    int og=0;
                    for(auto &z : go[start]){
                        int w=1ll*(1ll*prec[z[0]][x1]*prec[z[1]][x2]%M)*prec[z[2]][x3]%M;
                        add(og,w);
                    }
                    og=mult(og,mult(n-j,i+1));
                    og=mult(og,p2[x0]);
                    if(i!=j) og=mult(2,og);
                    add(s,og);
                }
            }
            add(ans,mult(p2[b1+b2],s));
        }
    }
    cout<<ans;
    return 0;
}
/*
5
1 2 3 4 5
1
1 4 3

*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4676 KB Output is correct
2 Correct 172 ms 4556 KB Output is correct
3 Correct 166 ms 4628 KB Output is correct
4 Correct 164 ms 4628 KB Output is correct
5 Correct 165 ms 4556 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4676 KB Output is correct
2 Correct 172 ms 4556 KB Output is correct
3 Correct 166 ms 4628 KB Output is correct
4 Correct 164 ms 4628 KB Output is correct
5 Correct 165 ms 4556 KB Output is correct
6 Correct 175 ms 4636 KB Output is correct
7 Correct 182 ms 4556 KB Output is correct
8 Correct 179 ms 4556 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 267 ms 6600 KB Output is correct
2 Correct 191 ms 4832 KB Output is correct
3 Correct 179 ms 4644 KB Output is correct
4 Correct 181 ms 4628 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 4652 KB Output is correct
2 Correct 1230 ms 4640 KB Output is correct
3 Correct 1212 ms 4644 KB Output is correct
4 Correct 1221 ms 4644 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4556 KB Output is correct
2 Correct 170 ms 4632 KB Output is correct
3 Correct 169 ms 4676 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4556 KB Output is correct
2 Correct 170 ms 4632 KB Output is correct
3 Correct 169 ms 4676 KB Output is correct
4 Correct 172 ms 4736 KB Output is correct
5 Correct 177 ms 4812 KB Output is correct
6 Correct 176 ms 4732 KB Output is correct
7 Correct 175 ms 4804 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4676 KB Output is correct
2 Correct 172 ms 4556 KB Output is correct
3 Correct 166 ms 4628 KB Output is correct
4 Correct 164 ms 4628 KB Output is correct
5 Correct 165 ms 4556 KB Output is correct
6 Correct 175 ms 4636 KB Output is correct
7 Correct 182 ms 4556 KB Output is correct
8 Correct 179 ms 4556 KB Output is correct
9 Correct 168 ms 4556 KB Output is correct
10 Correct 170 ms 4632 KB Output is correct
11 Correct 169 ms 4676 KB Output is correct
12 Correct 181 ms 4636 KB Output is correct
13 Correct 184 ms 4644 KB Output is correct
14 Correct 177 ms 4636 KB Output is correct
15 Correct 179 ms 4636 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4676 KB Output is correct
2 Correct 172 ms 4556 KB Output is correct
3 Correct 166 ms 4628 KB Output is correct
4 Correct 164 ms 4628 KB Output is correct
5 Correct 165 ms 4556 KB Output is correct
6 Correct 175 ms 4636 KB Output is correct
7 Correct 182 ms 4556 KB Output is correct
8 Correct 179 ms 4556 KB Output is correct
9 Correct 168 ms 4556 KB Output is correct
10 Correct 170 ms 4632 KB Output is correct
11 Correct 169 ms 4676 KB Output is correct
12 Correct 172 ms 4736 KB Output is correct
13 Correct 177 ms 4812 KB Output is correct
14 Correct 176 ms 4732 KB Output is correct
15 Correct 175 ms 4804 KB Output is correct
16 Correct 181 ms 4636 KB Output is correct
17 Correct 184 ms 4644 KB Output is correct
18 Correct 177 ms 4636 KB Output is correct
19 Correct 179 ms 4636 KB Output is correct
20 Correct 611 ms 6512 KB Output is correct
21 Correct 550 ms 6608 KB Output is correct
22 Correct 517 ms 6512 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4676 KB Output is correct
2 Correct 172 ms 4556 KB Output is correct
3 Correct 166 ms 4628 KB Output is correct
4 Correct 164 ms 4628 KB Output is correct
5 Correct 165 ms 4556 KB Output is correct
6 Correct 175 ms 4636 KB Output is correct
7 Correct 182 ms 4556 KB Output is correct
8 Correct 179 ms 4556 KB Output is correct
9 Correct 267 ms 6600 KB Output is correct
10 Correct 191 ms 4832 KB Output is correct
11 Correct 179 ms 4644 KB Output is correct
12 Correct 181 ms 4628 KB Output is correct
13 Correct 1252 ms 4652 KB Output is correct
14 Correct 1230 ms 4640 KB Output is correct
15 Correct 1212 ms 4644 KB Output is correct
16 Correct 1221 ms 4644 KB Output is correct
17 Correct 168 ms 4556 KB Output is correct
18 Correct 170 ms 4632 KB Output is correct
19 Correct 169 ms 4676 KB Output is correct
20 Correct 172 ms 4736 KB Output is correct
21 Correct 177 ms 4812 KB Output is correct
22 Correct 176 ms 4732 KB Output is correct
23 Correct 175 ms 4804 KB Output is correct
24 Correct 181 ms 4636 KB Output is correct
25 Correct 184 ms 4644 KB Output is correct
26 Correct 177 ms 4636 KB Output is correct
27 Correct 179 ms 4636 KB Output is correct
28 Correct 611 ms 6512 KB Output is correct
29 Correct 550 ms 6608 KB Output is correct
30 Correct 517 ms 6512 KB Output is correct
31 Correct 1481 ms 6596 KB Output is correct
32 Correct 1356 ms 7680 KB Output is correct
33 Correct 1383 ms 7620 KB Output is correct
34 Correct 1382 ms 7496 KB Output is correct
35 Correct 1514 ms 7532 KB Output is correct
36 Correct 1393 ms 7492 KB Output is correct