oj.uz

Submission #441163

# Submission time Handle Problem Language Result Execution time Memory
441163 2021-07-04T13:00:37 Z leaked Intergalactic ship (IZhO19_xorsum) C++14
92 / 100
 2000 ms 7588 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]]++;
                if(s&1) lol[1].pref[l[i]]++,lol[1].pref[r[i]+1]--;
                if(s&2) lol[2].pref[r[i]+1]--,lol[2].pref[l[i]]++;
            }
            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[3]=st.get(0,i,j,n-1);
                    cnt[1]=lol[1].get(i)-cnt[3];
                    cnt[2]=+lol[2].get(j)-cnt[3];
                    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 191 ms 4556 KB Output is correct
2 Correct 193 ms 4556 KB Output is correct
3 Correct 194 ms 4676 KB Output is correct
4 Correct 193 ms 4632 KB Output is correct
5 Correct 192 ms 4676 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4556 KB Output is correct
2 Correct 193 ms 4556 KB Output is correct
3 Correct 194 ms 4676 KB Output is correct
4 Correct 193 ms 4632 KB Output is correct
5 Correct 192 ms 4676 KB Output is correct
6 Correct 215 ms 4636 KB Output is correct
7 Correct 205 ms 4636 KB Output is correct
8 Correct 206 ms 4632 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 6604 KB Output is correct
2 Correct 220 ms 4828 KB Output is correct
3 Correct 208 ms 4648 KB Output is correct
4 Correct 207 ms 4640 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1944 ms 4652 KB Output is correct
2 Correct 1921 ms 4644 KB Output is correct
3 Correct 1890 ms 4644 KB Output is correct
4 Correct 1887 ms 4640 KB Output is correct

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4640 KB Output is correct
2 Correct 193 ms 4648 KB Output is correct
3 Correct 192 ms 4556 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 4640 KB Output is correct
2 Correct 193 ms 4648 KB Output is correct
3 Correct 192 ms 4556 KB Output is correct
4 Correct 198 ms 4736 KB Output is correct
5 Correct 201 ms 4740 KB Output is correct
6 Correct 197 ms 4684 KB Output is correct
7 Correct 196 ms 4740 KB Output is correct

Subtask #7
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4556 KB Output is correct
2 Correct 193 ms 4556 KB Output is correct
3 Correct 194 ms 4676 KB Output is correct
4 Correct 193 ms 4632 KB Output is correct
5 Correct 192 ms 4676 KB Output is correct
6 Correct 215 ms 4636 KB Output is correct
7 Correct 205 ms 4636 KB Output is correct
8 Correct 206 ms 4632 KB Output is correct
9 Correct 194 ms 4640 KB Output is correct
10 Correct 193 ms 4648 KB Output is correct
11 Correct 192 ms 4556 KB Output is correct
12 Correct 218 ms 4640 KB Output is correct
13 Correct 219 ms 4644 KB Output is correct
14 Correct 210 ms 4556 KB Output is correct
15 Correct 209 ms 4556 KB Output is correct

Subtask #8
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4556 KB Output is correct
2 Correct 193 ms 4556 KB Output is correct
3 Correct 194 ms 4676 KB Output is correct
4 Correct 193 ms 4632 KB Output is correct
5 Correct 192 ms 4676 KB Output is correct
6 Correct 215 ms 4636 KB Output is correct
7 Correct 205 ms 4636 KB Output is correct
8 Correct 206 ms 4632 KB Output is correct
9 Correct 194 ms 4640 KB Output is correct
10 Correct 193 ms 4648 KB Output is correct
11 Correct 192 ms 4556 KB Output is correct
12 Correct 198 ms 4736 KB Output is correct
13 Correct 201 ms 4740 KB Output is correct
14 Correct 197 ms 4684 KB Output is correct
15 Correct 196 ms 4740 KB Output is correct
16 Correct 218 ms 4640 KB Output is correct
17 Correct 219 ms 4644 KB Output is correct
18 Correct 210 ms 4556 KB Output is correct
19 Correct 209 ms 4556 KB Output is correct
20 Correct 803 ms 6488 KB Output is correct
21 Correct 752 ms 6640 KB Output is correct
22 Correct 724 ms 6608 KB Output is correct

Subtask #9
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 4556 KB Output is correct
2 Correct 193 ms 4556 KB Output is correct
3 Correct 194 ms 4676 KB Output is correct
4 Correct 193 ms 4632 KB Output is correct
5 Correct 192 ms 4676 KB Output is correct
6 Correct 215 ms 4636 KB Output is correct
7 Correct 205 ms 4636 KB Output is correct
8 Correct 206 ms 4632 KB Output is correct
9 Correct 303 ms 6604 KB Output is correct
10 Correct 220 ms 4828 KB Output is correct
11 Correct 208 ms 4648 KB Output is correct
12 Correct 207 ms 4640 KB Output is correct
13 Correct 1944 ms 4652 KB Output is correct
14 Correct 1921 ms 4644 KB Output is correct
15 Correct 1890 ms 4644 KB Output is correct
16 Correct 1887 ms 4640 KB Output is correct
17 Correct 194 ms 4640 KB Output is correct
18 Correct 193 ms 4648 KB Output is correct
19 Correct 192 ms 4556 KB Output is correct
20 Correct 198 ms 4736 KB Output is correct
21 Correct 201 ms 4740 KB Output is correct
22 Correct 197 ms 4684 KB Output is correct
23 Correct 196 ms 4740 KB Output is correct
24 Correct 218 ms 4640 KB Output is correct
25 Correct 219 ms 4644 KB Output is correct
26 Correct 210 ms 4556 KB Output is correct
27 Correct 209 ms 4556 KB Output is correct
28 Correct 803 ms 6488 KB Output is correct
29 Correct 752 ms 6640 KB Output is correct
30 Correct 724 ms 6608 KB Output is correct
31 Execution timed out 2079 ms 7588 KB Time limit exceeded
32 Halted 0 ms 0 KB -