Submission #1196837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196837		InvMOD	즐거운 사진 수집 (JOI13_collecting)	C++17	0 / 100	984 ms	269768 KiB

collecting

#include<bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define eb emplace_back

#define vi vector<int>
#define pi pair<int,int>
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())

template<class T> using upq = priority_queue<T, vector<T>, greater<T>>;
template<class T> int lwrbound(const vector<T>& a, const T& b, const int s = 0){return int(lower_bound(s + all(a), b) - a.begin());}
template<class T> int uprbound(const vector<T>& a, const T& b, const int s = 0){return int(upper_bound(s + all(a), b) - a.begin());}

#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define ROF(i, a, b) for(int i = (a); i >= (b); i--)
#define sumof(x) accumulate(all(x), 0ll)
#define dbg(x) "[" << #x " = " << (x) << "]"
#define el "\n"

using ll = long long;
using ld = long double;

template<class T> bool ckmx(T& a, const T b){return (a < b ? a = b, true : false);}
template<class T> bool ckmn(T& a, const T b){return (a > b ? a = b, true : false);}

const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = numeric_limits<ll>::max() / 8;


/*  (i, j): state of col i vs row j

    calculate the number that has (1, 0) or (0, 1) is hard
    so we will calculate which has both (0,0) and (1,1)
*/

struct SMT{
    vector<int> st, cnt; int trsz;

    SMT(int n = 0): trsz(1 << n), st(trsz << 2 | 1), cnt(n) {
        for(int i = 0; i < n; i++){
            cnt[i] = (1 << i);
        }
    }

    void update(int id, int l, int r, int x, int depth){
        if(l == r){
            st[id] ^= 1;
        }
        else{
            int m = l+r>>1;
            if(x <= m)
                update(id << 1, l, m, x, depth + 1);
            else update(id << 1|1, m+1, r, x, depth + 1);

            assert(depth < sz(cnt));
            if(st[id] < 2) --cnt[depth];

            if(max(st[id << 1], st[id << 1|1]) > 1){
                st[id] = 2;
            }
            else{
                if(st[id << 1] == st[id << 1|1]){
                    st[id] = st[id << 1];
                    ++cnt[depth];
                }
                else st[id] = 2;
            }
            //cout << id <<" " << l <<" " << r <<" " << cnt[depth] << el;
        }
    }

    void update(int x){
        update(1, 1, trsz, x, 0);
    }

    ll query(int x){
        return cnt[x];
    }
};


void Main()
{
    int n, q; cin >> n >> q;

    vector<SMT> tr(2, SMT(n));
    while(q--){
        int t,x; cin >> t >> x;

        tr[t].update(x);

        ll ans = 0;
        for(int i = 0; i < n; i++){
            ans += (1ll << i) * (1ll << i);
            ans -= tr[0].query(i) * tr[1].query(i);

            //cout << (1ll << i) * (1ll << i) <<" " << tr[0].query(i) <<" " << tr[1].query(i) << el;
        }
        // assume each point will become a square when (sum of compress of four photo) + 1

        cout << ans * 4 + 1 << el;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }

    int t = 1; while(t--) Main();
    return 0;
}

Compilation message (stderr)

collecting.cpp: In function 'int32_t main()':
collecting.cpp:119:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |         freopen(name".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
collecting.cpp:120:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         freopen(name".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70