Ideone.com

fork download

copy

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
 
const ll N = (1ll << 20), M = 20, K = 10001, OO = 1e18l, L = 18, MOD = 1e9 + 7, sumD = 6638449;
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
template<typename K, typename V, typename Comp = less<K>>
using ordered_map = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template<typename K, typename Comp = less<K>>
using ordered_set = ordered_map<K, null_type, Comp>;
 
template<typename K, typename V, typename Comp = less_equal<K>>
using ordered_multimap = tree<K, V, Comp, rb_tree_tag, tree_order_statistics_node_update>;
template<typename K, typename Comp = less_equal<K>>
using ordered_multiset = ordered_multimap<K, null_type, Comp>;
 
void solve() {
    int n, m, q, x, y;
    cin >> n >> m >> q;
    string s;
    vector<set<int>> ones(n);
    ordered_multiset<int> os;
 
    for (int i = 0; i < n; i++) {
        cin >> s;
        s = '1' + s;
        reverse(s.begin(), s.end());
        for (int j = 0; j <= m; j++)
            if (s[j] == '1') ones[i].insert(j);
        os.insert(*ones[i].begin());
    }
 
    auto flip = [&](int i, int j) -> void {
        auto it = ones[i].find(j);
        if (it != ones[i].end()) {
 
            if (it == ones[i].begin()) {
                ones[i].erase(it);
                os.erase(os.find_by_order(os.order_of_key(j)));
                os.insert(*ones[i].begin());
            }else{
                ones[i].erase(j);
            }
 
 
        } else {
 
            auto mn = *ones[i].begin();
            if (mn > j) {
                os.erase(os.find_by_order(os.order_of_key(mn)));
                os.insert(j);
            }
            ones[i].insert(j);
 
        }
    };
 
 
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            cin >> x >> y;
            flip(x, y);
        } else {
            cin >> x;
            cout << os.size() - os.order_of_key(x) << "\n";
        }
    }
}
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    ll t = 1;
    cin >> t;
    while (t--) { solve(); cout << "\n";}
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsbCBsb25nIGxvbmcgaW50Cgpjb25zdCBsbCBOID0gKDFsbCA8PCAyMCksIE0gPSAyMCwgSyA9IDEwMDAxLCBPTyA9IDFlMThsLCBMID0gMTgsIE1PRCA9IDFlOSArIDcsIHN1bUQgPSA2NjM4NDQ5OwoKI2luY2x1ZGUgPGV4dC9wYl9kcy9hc3NvY19jb250YWluZXIuaHBwPgojaW5jbHVkZSA8ZXh0L3BiX2RzL3RyZWVfcG9saWN5LmhwcD4KdXNpbmcgbmFtZXNwYWNlIF9fZ251X3BiZHM7Cgp0ZW1wbGF0ZTx0eXBlbmFtZSBLLCB0eXBlbmFtZSBWLCB0eXBlbmFtZSBDb21wID0gbGVzczxLPj4KdXNpbmcgb3JkZXJlZF9tYXAgPSB0cmVlPEssIFYsIENvbXAsIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+Owp0ZW1wbGF0ZTx0eXBlbmFtZSBLLCB0eXBlbmFtZSBDb21wID0gbGVzczxLPj4KdXNpbmcgb3JkZXJlZF9zZXQgPSBvcmRlcmVkX21hcDxLLCBudWxsX3R5cGUsIENvbXA+OwoKdGVtcGxhdGU8dHlwZW5hbWUgSywgdHlwZW5hbWUgViwgdHlwZW5hbWUgQ29tcCA9IGxlc3NfZXF1YWw8Sz4+CnVzaW5nIG9yZGVyZWRfbXVsdGltYXAgPSB0cmVlPEssIFYsIENvbXAsIHJiX3RyZWVfdGFnLCB0cmVlX29yZGVyX3N0YXRpc3RpY3Nfbm9kZV91cGRhdGU+Owp0ZW1wbGF0ZTx0eXBlbmFtZSBLLCB0eXBlbmFtZSBDb21wID0gbGVzc19lcXVhbDxLPj4KdXNpbmcgb3JkZXJlZF9tdWx0aXNldCA9IG9yZGVyZWRfbXVsdGltYXA8SywgbnVsbF90eXBlLCBDb21wPjsKCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgbiwgbSwgcSwgeCwgeTsKICAgIGNpbiA+PiBuID4+IG0gPj4gcTsKICAgIHN0cmluZyBzOwogICAgdmVjdG9yPHNldDxpbnQ+PiBvbmVzKG4pOwogICAgb3JkZXJlZF9tdWx0aXNldDxpbnQ+IG9zOwoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgY2luID4+IHM7CiAgICAgICAgcyA9ICcxJyArIHM7CiAgICAgICAgcmV2ZXJzZShzLmJlZ2luKCksIHMuZW5kKCkpOwogICAgICAgIGZvciAoaW50IGogPSAwOyBqIDw9IG07IGorKykKICAgICAgICAgICAgaWYgKHNbal0gPT0gJzEnKSBvbmVzW2ldLmluc2VydChqKTsKICAgICAgICBvcy5pbnNlcnQoKm9uZXNbaV0uYmVnaW4oKSk7CiAgICB9CgogICAgYXV0byBmbGlwID0gWyZdKGludCBpLCBpbnQgaikgLT4gdm9pZCB7CiAgICAgICAgYXV0byBpdCA9IG9uZXNbaV0uZmluZChqKTsKICAgICAgICBpZiAoaXQgIT0gb25lc1tpXS5lbmQoKSkgewoKICAgICAgICAgICAgaWYgKGl0ID09IG9uZXNbaV0uYmVnaW4oKSkgewogICAgICAgICAgICAgICAgb25lc1tpXS5lcmFzZShpdCk7CiAgICAgICAgICAgICAgICBvcy5lcmFzZShvcy5maW5kX2J5X29yZGVyKG9zLm9yZGVyX29mX2tleShqKSkpOwogICAgICAgICAgICAgICAgb3MuaW5zZXJ0KCpvbmVzW2ldLmJlZ2luKCkpOwogICAgICAgICAgICB9ZWxzZXsKICAgICAgICAgICAgICAgIG9uZXNbaV0uZXJhc2Uoaik7CiAgICAgICAgICAgIH0KCgogICAgICAgIH0gZWxzZSB7CgogICAgICAgICAgICBhdXRvIG1uID0gKm9uZXNbaV0uYmVnaW4oKTsKICAgICAgICAgICAgaWYgKG1uID4gaikgewogICAgICAgICAgICAgICAgb3MuZXJhc2Uob3MuZmluZF9ieV9vcmRlcihvcy5vcmRlcl9vZl9rZXkobW4pKSk7CiAgICAgICAgICAgICAgICBvcy5pbnNlcnQoaik7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgb25lc1tpXS5pbnNlcnQoaik7CgogICAgICAgIH0KICAgIH07CgoKICAgIHdoaWxlIChxLS0pIHsKICAgICAgICBpbnQgdDsKICAgICAgICBjaW4gPj4gdDsKICAgICAgICBpZiAodCA9PSAxKSB7CiAgICAgICAgICAgIGNpbiA+PiB4ID4+IHk7CiAgICAgICAgICAgIGZsaXAoeCwgeSk7CiAgICAgICAgfSBlbHNlIHsKICAgICAgICAgICAgY2luID4+IHg7CiAgICAgICAgICAgIGNvdXQgPDwgb3Muc2l6ZSgpIC0gb3Mub3JkZXJfb2Zfa2V5KHgpIDw8ICJcbiI7CiAgICAgICAgfQogICAgfQp9CgpzaWduZWQgbWFpbigpIHsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKSwgY2luLnRpZShudWxscHRyKSwgY291dC50aWUobnVsbHB0cik7CiAgICBsbCB0ID0gMTsKICAgIGNpbiA+PiB0OwogICAgd2hpbGUgKHQtLSkgeyBzb2x2ZSgpOyBjb3V0IDw8ICJcbiI7fQp9

Success #stdin #stdout 0.01s 5288KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/1L8ZW2

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language