QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #63930 | #2831. Game Theory | pty6666 | RE | 3ms | 3412kb | C++14 | 3.6kb | 2022-11-23 18:28:23 | 2022-11-23 18:28:25 |
Judging History
answer
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <random>
#include <ctime>
#include <string>
#define lson ( p << 1 )
#define rson ( p << 1 | 1 )
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 10;
struct Tree{
ll val[2][2];
int lazy;
int cnt[2];
}tree[maxn << 2];
int n,q;
string s;
Tree combine(Tree x,Tree y)
{
Tree ret{};
for(int i = 0;i<=1;i++){
for(int j = 0;j<=1;j++){
ret.val[i][j] = x.val[i][j] + y.val[i][j];
}
ret.cnt[i] = x.cnt[i] + y.cnt[i];
}
return ret;
}
void pushdown(int p)
{
swap(tree[lson].val[0][0],tree[lson].val[1][0]);
swap(tree[lson].val[0][1],tree[lson].val[1][1]);
swap(tree[rson].val[0][0],tree[rson].val[1][0]);
swap(tree[rson].val[0][1],tree[rson].val[1][1]);
swap(tree[lson].cnt[0],tree[lson].cnt[1]);
swap(tree[rson].cnt[0],tree[rson].cnt[1]);
tree[lson].lazy ^= 1;
tree[rson].lazy ^= 1;
tree[p].lazy = 0;
}
void build(int l = 1,int r = n,int p = 1)
{
tree[p].lazy = 0;
if(l == r){
for(int i =0;i<=1;i++){
for(int j = 0;j<=1;j++){
tree[p].val[i][j] = 0;
}
tree[p].cnt[i] = 0;
}
if(s[l] == '0'){
tree[p].val[0][0] = l;
tree[p].val[0][1] = n - l + 1;
tree[p].cnt[0] = 1;
}
else {
tree[p].val[1][0] = l;
tree[p].val[1][1] = n - l + 1;
tree[p].cnt[1] = 1;
}
return;
}
int mid = (l + r) >> 1;
build(l,mid,lson);
build(mid + 1,r,rson);
for(int i = 0;i<=1;i++){
for(int j = 0;j<=1;j++){
tree[p].val[i][j] = tree[lson].val[i][j] + tree[rson].val[i][j];
}
tree[p].cnt[i] = tree[lson].cnt[i] + tree[rson].cnt[i];
}
}
void update(int s,int t,int l = 1,int r = n,int p = 1)
{
if(s <= l && r <= t){
tree[p].lazy ^= 1;
swap(tree[p].val[0][0],tree[p].val[1][0]);
swap(tree[p].val[0][1],tree[p].val[1][1]);
swap(tree[p].cnt[0],tree[p].cnt[1]);
return;
}
int mid = (l +r ) >> 1;
if(tree[p].lazy)
pushdown(p);
if(s <= mid)
update(s,t,l,mid,lson);
if(t > mid)
update(s,t,mid + 1,r,rson);
for(int i = 0;i<=1;i++){
for(int j = 0;j<=1;j++){
tree[p].val[i][j] = tree[lson].val[i][j] + tree[rson].val[i][j];
}
tree[p].cnt[i] = tree[lson].cnt[i] + tree[rson].cnt[i];
}
}
Tree query(int s,int t,int l = 1,int r = n,int p = 1)
{
if(s <= l && r <= t){
return tree[p];
}
if(tree[p].lazy)
pushdown(p);
int mid = ( l + r) >> 1;
if(s <= mid && t > mid)
return combine(query(s,t,l,mid,lson), query(s,t,mid + 1,r,rson));
else if(s <= mid)
return query(s,t,l,mid,lson);
else return query(s,t,mid + 1,r,rson);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
while(cin >> n >> q){
cin >> s;
s = " " + s;
build();
for(int i = 1;i<=q;i++){
int l,r;
cin >> l >> r;
update(l,r);
Tree temp = query(1,n);
int k = temp.cnt[1];
if(k == 0){
cout << 0 << "\n";
}
Tree tt = query(k,k);
ll ans = 0;
if(tt.cnt[1] == 1) {
Tree temp1 {};
if ( k - 1 >= 1 )
temp1 = query( 1, k - 1 );
Tree temp2 = query(k,n);
ans += temp2.val[1][0] - temp1.val[0][0];
temp2 = {};
if(k + 1 <= n)
temp2 = query(k + 1,n);
ans += temp1.val[0][1] - temp2.val[1][1];
cout << ans << "\n";
}
else {
Tree temp1 = query( 1, k );
Tree temp2{};
if(k + 1 <= n){
temp2 = query(k + 1,n);
}
ans += temp1.val[0][1] - temp2.val[1][1];
temp1 = {};
if(k - 1 >= 1)
temp1 = query(1,k - 1);
ans += temp2.val[1][0] - temp1.val[0][0];
cout << ans << "\n";
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3412kb
input:
3 2 010 1 2 2 3 5 1 00000 1 5
output:
1 3 5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 3324kb
input:
1 1 0 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: -100
Runtime Error
input:
2 2 01 2 2 2 2 2 2 01 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 1 2 2 00 1 2 1 2 2 2 11 1 2 1 2 2 2 01 2 2 1 1 2 2 10 2 2 1 2 2 2 01 1 2 1 2 1 2 0 1 1 1 1 2 2 01 1 2 2 2 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 2 1 1 1 2 0 1 1 1 1 2 2 01 1 2 1 2 2 2 10 1 2 1 1 1 2 0 1 1 1 1 1 2 0 1 1 1 1 1 2 1 1 1 1 1 2 2 10 1 ...