oj.uz

Submission #441161

# Submission time Handle Problem Language Result Execution time Memory
441161 2021-07-04T12:56:53 Z leaked Intergalactic ship (IZhO19_xorsum) C++14
83 / 100
 2000 ms 7684 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[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 169 ms 4556 KB Output is correct
2 Correct 165 ms 4556 KB Output is correct
3 Correct 171 ms 4556 KB Output is correct
4 Correct 168 ms 4676 KB Output is correct
5 Correct 165 ms 4632 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4556 KB Output is correct
2 Correct 165 ms 4556 KB Output is correct
3 Correct 171 ms 4556 KB Output is correct
4 Correct 168 ms 4676 KB Output is correct
5 Correct 165 ms 4632 KB Output is correct
6 Correct 186 ms 4676 KB Output is correct
7 Correct 189 ms 4636 KB Output is correct
8 Correct 184 ms 4676 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 6600 KB Output is correct
2 Correct 193 ms 4912 KB Output is correct
3 Correct 191 ms 4556 KB Output is correct
4 Correct 187 ms 4644 KB Output is correct

Subtask #4
0 / 9.0

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

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 4676 KB Output is correct
2 Correct 179 ms 4636 KB Output is correct
3 Correct 178 ms 4636 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 4676 KB Output is correct
2 Correct 179 ms 4636 KB Output is correct
3 Correct 178 ms 4636 KB Output is correct
4 Correct 173 ms 4684 KB Output is correct
5 Correct 181 ms 4736 KB Output is correct
6 Correct 170 ms 4732 KB Output is correct
7 Correct 175 ms 4744 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4556 KB Output is correct
2 Correct 165 ms 4556 KB Output is correct
3 Correct 171 ms 4556 KB Output is correct
4 Correct 168 ms 4676 KB Output is correct
5 Correct 165 ms 4632 KB Output is correct
6 Correct 186 ms 4676 KB Output is correct
7 Correct 189 ms 4636 KB Output is correct
8 Correct 184 ms 4676 KB Output is correct
9 Correct 176 ms 4676 KB Output is correct
10 Correct 179 ms 4636 KB Output is correct
11 Correct 178 ms 4636 KB Output is correct
12 Correct 191 ms 4644 KB Output is correct
13 Correct 189 ms 4648 KB Output is correct
14 Correct 192 ms 4676 KB Output is correct
15 Correct 187 ms 4676 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4556 KB Output is correct
2 Correct 165 ms 4556 KB Output is correct
3 Correct 171 ms 4556 KB Output is correct
4 Correct 168 ms 4676 KB Output is correct
5 Correct 165 ms 4632 KB Output is correct
6 Correct 186 ms 4676 KB Output is correct
7 Correct 189 ms 4636 KB Output is correct
8 Correct 184 ms 4676 KB Output is correct
9 Correct 176 ms 4676 KB Output is correct
10 Correct 179 ms 4636 KB Output is correct
11 Correct 178 ms 4636 KB Output is correct
12 Correct 173 ms 4684 KB Output is correct
13 Correct 181 ms 4736 KB Output is correct
14 Correct 170 ms 4732 KB Output is correct
15 Correct 175 ms 4744 KB Output is correct
16 Correct 191 ms 4644 KB Output is correct
17 Correct 189 ms 4648 KB Output is correct
18 Correct 192 ms 4676 KB Output is correct
19 Correct 187 ms 4676 KB Output is correct
20 Correct 794 ms 6612 KB Output is correct
21 Correct 720 ms 7684 KB Output is correct
22 Correct 726 ms 7580 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 4556 KB Output is correct
2 Correct 165 ms 4556 KB Output is correct
3 Correct 171 ms 4556 KB Output is correct
4 Correct 168 ms 4676 KB Output is correct
5 Correct 165 ms 4632 KB Output is correct
6 Correct 186 ms 4676 KB Output is correct
7 Correct 189 ms 4636 KB Output is correct
8 Correct 184 ms 4676 KB Output is correct
9 Correct 261 ms 6600 KB Output is correct
10 Correct 193 ms 4912 KB Output is correct
11 Correct 191 ms 4556 KB Output is correct
12 Correct 187 ms 4644 KB Output is correct
13 Execution timed out 2009 ms 4648 KB Time limit exceeded
14 Halted 0 ms 0 KB -