Submission #395191

#	Time	Username	Problem	Language	Result	Execution time	Memory
395191		NekoRolly	Intergalactic ship (IZhO19_xorsum)	C++17	26 / 100	1143 ms	5068 KiB

xorsum

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define fp(i,a,b) for(ll i=a ; i<b ; i++)
#define fn(i,a,b) for(int i=a ; i>=b ; i--)
#define ones(x) __builtin_popcount(x)
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define dbg(x) cout << (#x) << " = " << x << " "
#define fini cout << "\n";
#define line cout << "-----------------------------------\n";
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int read (){
    int x = 0, f = 1; char s = getchar();while (s < '0' || s > '9') {if (s == '-') f = -1; s = getchar();}
    while (s >= '0' && s <= '9') x = x * 10 + s - '0', s = getchar();
    return x * f; 
}

const ll M=1e5+7;
const ll N=1e3+7;
const ll inf=1e9;
const ll mod=1e9+7;
const ll mod2=998244353;

struct rng{
	int l,r,x;
};
int n,q;
int a[N];
rng qs[M];
int c[N][N],c1[N],c2[N];
ll b[4],z[4];
ll e[M];
ll ans;

ll pro(ll a,ll b){
	return (a*b)%mod;
}

void go(int ide){
	cin >> n;
	fp(i,1,n+1) cin >> a[i];

	cin >> q;
	fp(i,1,q+1) cin >> qs[i].l >> qs[i].r >> qs[i].x;

	e[0] = 1;
	fp(i,1,M) e[i] = (e[i-1]*2)%mod;

	fp(k1,0,7) fp(k2,0,7){
		fp(i,1,n+1){
			fp(j,1,n+1) c[i][j] = 0;
			c1[i] = c2[i] = 0;
		}

		fp(i,1,q+1){
			int l = qs[i].l;
			int r = qs[i].r;
			if (1<<k1&qs[i].x) c1[l]++, c1[r+1]--;
			if (1<<k2&qs[i].x) c2[l]++, c2[r+1]--;
			if ((1<<k1&qs[i].x) && (1<<k2&qs[i].x)){
				c[l][l]++;
				c[l][r+1]--;
				c[r+1][l]--;
				c[r+1][r+1]++;
			}
		}

		fp(i,1,n+1){
			c1[i] += c1[i-1];
			c2[i] += c2[i-1];
			fp(j,1,n+1) c[i][j] += c[i][j-1] + c[i-1][j] - c[i-1][j-1];
		}

		fp(i,1,n+1) fp(j,1,n+1){
			z[3] = c[i][j];
			z[2] = c1[i] - c[i][j];
			z[1] = c2[j] - c[i][j];
			z[0] = q - c1[i] - c2[j] + c[i][j];

			fp(k,0,4) b[k] = 0;
			b[2*(a[i]>>k1&1) + (a[j]>>k2&1)] = e[z[0]];
			int cont = (z[1]>0) + (z[2]>0) + (z[3]>0);
			if (cont>1) b[3] = e[q-2];
			else{
				if (z[1]) b[3] = e[z[1]-1]*(b[3]+b[2]);
				if (z[2]) b[3] = e[z[2]-1]*(b[3]+b[1]);
				if (z[3]) b[3] = e[z[3]-1]*(b[3]+b[0]);
			}

			ans = (ans + pro(e[k1+k2], pro(pro(min(i,j), n-max(i,j)+1), b[3])))%mod;
			// dbg(ans); fini;
		}
		// line;
	}

	cout << ans << "\n";
}

int main(){
    fastio;
    int tst=1;
    // cin >> tst;
    // cout << fixed << setprecision(12);

    fp(i,0,tst) go(i+1);
  
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 6
• Subtask 4: 9 / 9
• Subtask 5: 8 / 8
• Subtask 6: 0 / 11
• Subtask 7: 0 / 19
• Subtask 8: 0 / 30
• Subtask 9: 0 / 8