oj.uz

답안 #395165

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
395165 2021-04-27T23:53:20 Z NekoRolly Intergalactic ship (IZhO19_xorsum) C++17
0 / 100
 1891 ms 5052 KB 
#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)&(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)]++;

			fp(k,0,4) b[k] = (b[k]*e[z[0]])%mod;
			if (z[1]){
				b[0] = b[1] = (e[z[1]-1]*(b[0] + b[1]))%mod;
				b[2] = b[3] = (e[z[1]-1]*(b[2] + b[3]))%mod;
			}
			if (z[2]){
				b[0] = b[2] = (e[z[2]-1]*(b[0]+b[2]))%mod;
				b[1] = b[3] = (e[z[2]-1]*(b[1]+b[3]))%mod;
			}
			if (z[3]){
				b[0] = b[3] = (e[z[3]-1]*(b[0]+b[3]))%mod;
				b[1] = b[2] = (e[z[3]-1]*(b[1]+b[2]))%mod;
			}

			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
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 2 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 2 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 2668 KB Output is correct
2 Correct 30 ms 1620 KB Output is correct
3 Incorrect 21 ms 1520 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1891 ms 5052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 2 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 2 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1100 KB Output is correct
2 Correct 1 ms 1100 KB Output is correct
3 Incorrect 2 ms 1116 KB Output isn't correct
4 Halted 0 ms 0 KB -