oj.uz

Submission #441159

# Submission time Handle Problem Language Result Execution time Memory
441159 2021-07-04T12:56:02 Z leaked Intergalactic ship (IZhO19_xorsum) C++14
56 / 100
 1990 ms 7672 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+1;
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[3];
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]);
        }
    }
    auto stupid=[&](int b1,int b2,int i,int j){
        vec<int>cnt(4,0);
        for(int t=0;t<q;t++){
            if(l[t]<=i && r[t]>=j){
                if((x[t]&pw(b1)) && (x[t]&pw(b2))) cnt[3]++;
                else if(x[t]&pw(b1)) cnt[1]++;
                else if(x[t]&pw(b2)) cnt[2]++;
                else cnt[0]++;
            }
            else if(r[t]<j && l[t]<=i && r[t]>=i){
                if(x[t]&pw(b1)) cnt[1]++;
                else cnt[0]++;
            }
            else if(l[t]>i && l[t]<=j && r[t]>=j){
                if(x[t]&pw(b2)) cnt[2]++;
                else cnt[0]++;
            }
            else{
                cnt[0]++;
            }
        }
        return cnt;
    };
    int ans=0;
    for(int b1=0;b1<7;b1++){
        for(int b2=0;b2<7;b2++){
            st.clr();
            for(int j=1;j<=2;j++) lol[j].clr();
            for(int i=0;i<q;i++){
                int f=(x[i]>>b1)&1;
                int s=(x[i]>>b2)&1;
                s<<=1;s+=f;
                if(s==3) st.pref[l[i]][r[i]]++;
                else if(s>0) lol[s].pref[l[i]]++,lol[s].pref[r[i]+1]--;
            }
            st.build();
            for(int i=1;i<=2;i++) lol[i].build();
            vec<int>cnt(4,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);
                    cnt[1]=st.get(0,i,i,j-1)+lol[1].get(i);
                    cnt[2]=st.get(i+1,j,j,n-1)+lol[2].get(j);
                    cnt[3]=st.get(0,i,j,n-1);
                    cnt[0]=(q-cnt[1]-cnt[2]-cnt[3]);
                    for(auto &z : go[start]){
                        int w=p2[cnt[0]];
                        w=mult(w,mult(prec[z[0]][cnt[1]],prec[z[1]][cnt[2]]));
                        w=mult(w,prec[z[2]][cnt[3]]);
                        if(i!=j) w=mult(2,w);
                        w=mult(n-j,mult(i+1,w));
                        add(ans,mult(w,p2[b1+b2]));
                    }
                }
            }
        }
    }
    cout<<ans;
    return 0;
}
/*
5
1 2 3 4 5
1
1 4 3

*/

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:115:10: warning: variable 'stupid' set but not used [-Wunused-but-set-variable]
  115 |     auto stupid=[&](int b1,int b2,int i,int j){
      |          ^~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4556 KB Output is correct
2 Correct 165 ms 4648 KB Output is correct
3 Correct 165 ms 4556 KB Output is correct
4 Correct 169 ms 4640 KB Output is correct
5 Correct 168 ms 4556 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4556 KB Output is correct
2 Correct 165 ms 4648 KB Output is correct
3 Correct 165 ms 4556 KB Output is correct
4 Correct 169 ms 4640 KB Output is correct
5 Correct 168 ms 4556 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 186 ms 4556 KB Output is correct
8 Correct 182 ms 4688 KB Output is correct

Subtask #3
0 / 6.0

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

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1981 ms 4676 KB Output is correct
2 Correct 1990 ms 4656 KB Output is correct
3 Correct 1951 ms 4648 KB Output is correct
4 Correct 1959 ms 4644 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4640 KB Output is correct
2 Correct 167 ms 4640 KB Output is correct
3 Correct 175 ms 4644 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 4640 KB Output is correct
2 Correct 167 ms 4640 KB Output is correct
3 Correct 175 ms 4644 KB Output is correct
4 Correct 174 ms 4684 KB Output is correct
5 Correct 170 ms 4684 KB Output is correct
6 Correct 177 ms 4780 KB Output is correct
7 Correct 185 ms 4776 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4556 KB Output is correct
2 Correct 165 ms 4648 KB Output is correct
3 Correct 165 ms 4556 KB Output is correct
4 Correct 169 ms 4640 KB Output is correct
5 Correct 168 ms 4556 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 186 ms 4556 KB Output is correct
8 Correct 182 ms 4688 KB Output is correct
9 Correct 168 ms 4640 KB Output is correct
10 Correct 167 ms 4640 KB Output is correct
11 Correct 175 ms 4644 KB Output is correct
12 Correct 202 ms 4648 KB Output is correct
13 Correct 191 ms 4652 KB Output is correct
14 Correct 196 ms 4648 KB Output is correct
15 Correct 193 ms 4644 KB Output is correct

Subtask #8
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4556 KB Output is correct
2 Correct 165 ms 4648 KB Output is correct
3 Correct 165 ms 4556 KB Output is correct
4 Correct 169 ms 4640 KB Output is correct
5 Correct 168 ms 4556 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 186 ms 4556 KB Output is correct
8 Correct 182 ms 4688 KB Output is correct
9 Correct 168 ms 4640 KB Output is correct
10 Correct 167 ms 4640 KB Output is correct
11 Correct 175 ms 4644 KB Output is correct
12 Correct 174 ms 4684 KB Output is correct
13 Correct 170 ms 4684 KB Output is correct
14 Correct 177 ms 4780 KB Output is correct
15 Correct 185 ms 4776 KB Output is correct
16 Correct 202 ms 4648 KB Output is correct
17 Correct 191 ms 4652 KB Output is correct
18 Correct 196 ms 4648 KB Output is correct
19 Correct 193 ms 4644 KB Output is correct
20 Incorrect 811 ms 7672 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 4556 KB Output is correct
2 Correct 165 ms 4648 KB Output is correct
3 Correct 165 ms 4556 KB Output is correct
4 Correct 169 ms 4640 KB Output is correct
5 Correct 168 ms 4556 KB Output is correct
6 Correct 186 ms 4640 KB Output is correct
7 Correct 186 ms 4556 KB Output is correct
8 Correct 182 ms 4688 KB Output is correct
9 Incorrect 264 ms 6724 KB Output isn't correct
10 Halted 0 ms 0 KB -