Submission #475540

#	Time	Username	Problem	Language	Result	Execution time	Memory
475540		leaked	Plus Minus (BOI17_plusminus)	C++14	12 / 100	2 ms	588 KiB

plusminus

#include <bits/stdc++.h>

#define m_p make_pair
#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<x)
#define sz(x) (int)x.size()
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef long double ld;
typedef pair<long long,long long> pll;
template <class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template <class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}
auto rng=bind(uniform_int_distribution<int>(1,20),mt19937(time(0)));
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
const int M=998244353;
const int N=1e6+100;
//#define int long long
//int cnt[2][N][2];
map<int,map<int,int>> cnt[2];

void paint(map<int,map<int,int>> &mp,int x,int c,int &is,int &c1){
    if(!mp[x][c] && mp[x][c^1]) is++;
    if(!mp[x][c] && !mp[x][c^1]) c1++;
    mp[x][c]++;
//    debug()<<imie(mp[x])imie(is);
}
void unpaint(map<int,map<int,int>> &mp,int x,int c,int &is,int &c1){
    if(mp[x][c]==1 && mp[x][c^1]) is--;
    assert(mp[x][c]>0);
    mp[x][c]--;
    if(!mp[x][c] && !mp[x][c^1]) c1--;
}
void add(int &a,int b){
    a+=b;
    if(a>=M) a-=M;
    else if(a<0) a+=M;
}
int mult(int a,int b){
    return 1ll*a*b%M;
}
//int p2[N];
int binpow(int a,int b){
    assert(a==2 && b>=0 && b<N);
    int ans=1;
    while(b){
        if(b&1) ans=mult(ans,a);
        b>>=1;a=mult(a,a);
    }
    return ans;
}
signed main(){
    fast_ioi;
//    p2[0]=1;
//    for(int i=1;i<N;i++) p2[i]=mult(p2[i-1],2);
//    while(1){
//    cout<<"NEW" <<endl;
    int n,m,q;
//    n=20,m=20, q=15;
    cin>>n>>m>>q;
//    cnt[0].resize(N);
//    for(int i=0;i<N;i++) cnt[0][i].assign(2,0);
//    cnt[1].resize(N);
//    for(int i=0;i<N;i++) cnt[1][i].assign(2,0);
    int k1=0,k2=0;
    int c1=0,c2=0;
        vec<int>cntt(2,0);
    auto get=[&](){
        assert(k1>=0&&k2>=0);
        if(k1 && k2) return 0;
        int ans=0;
        if(!k1){
            add(ans,binpow(2,n-c1));
    //        cerr<<binpow(2,n-sz(x))<<endl;
        }
        if(!k2){
            add(ans,binpow(2,m-c2));
    //        cerr<<binpow(2,m-sz(y))<<endl;
        }
//        if(!k1 && !k2) add(ans,-1);
//        if(!c1 && !c2) add(ans,-1);
//        debug()<<imie()
//        debug()<<imie(ans);
        for(auto &z : cntt)if(!z) add(ans,-1);
//        debug()<<imie(ans);
//        assert(ans>=0);
        return ans;
    };
    auto qpaint=[&](array<int,3>z){
        paint(cnt[0],z[0],(z[1]%2)^z[2],k1,c1);
        paint(cnt[1],z[1],(z[0]%2)^z[2],k2,c2);
        cntt[((z[0]+z[1])&1)^z[2]]++;
    };
    auto qunpaint=[&](array<int,3>z){
//        debug()<<imie(x)imie(y)imie(k1)imie(k2);
        unpaint(cnt[0],z[0],(z[1]%2)^z[2],k1,c1);
        unpaint(cnt[1],z[1],(z[0]%2)^z[2],k2,c2);
        cntt[((z[0]+z[1])&1)^z[2]]--;
//        debug()<<imie(x)imie(y)imie(k1)imie(k2);
    };
    map<pii,int>qp;


    while(q--){
        int a,b,c;
//        a=rng(),b=rng(),c=rng()%3-1;
//        if(!mp.count({a,b}) && c==-1) c=0;
//        cin>>a>>b>>c;
        char t;
        cin>>t>>a>>b;
        c=(t=='+'?1:0);
//        debug()<<imie(a)imie(b)imie(c);
        if(c==-1){
            if(qp.count({a,b})){
                qunpaint({a,b,qp[{a,b}]});
                qp.erase({a,b});
            }
        }
        else{
            if(qp.count({a,b})){
                qunpaint({a,b,qp[{a,b}]});
                qp.erase({a,b});
            }
            assert(!qp.count({a,b}));
            qpaint({a,b,c});
            qp[{a,b}]=c;
        }
//        debug()<<imie(qp);
//        asse
//        int fe=gos(-1);
//        assert(get()==gos(-1));
//        cout<<get()<<'\n';
//        debug()<<imie(x)imie(y);
    }
    cout<<get();
//    }
    return 0;
}
/*
3 3 3
2 1 0
2 3 1
3 3 1
*/

• Subtask 1: 12 / 12
• Subtask 2: 0 / 42
• Subtask 3: 0 / 46