oj.uz

Submission #64976

# Submission time Handle Problem Language Result Execution time Memory
64976 2018-08-06T10:51:29 Z forestryks Topovi (COCI15_topovi) C++
102 / 120
 2000 ms 34032 KB 
///////////////////////////////////////////////////////////////////////////////////////////////
#include <bits/stdc++.h>
using namespace std;

// #define int long long

#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define FILE_IO(x) freopen((string(x) + ".in").c_str(), "r", stdin); freopen((string(x) + ".out").c_str(), "w", stdout)
#define f first
#define s second
#define x1 x1qwer
#define y1 y1qwer
#define right right123
#define left left123
#define foreach(it, v) for (auto it : v)
#define rep(it, n) for (int it = 0; it < n; ++it)
#define forin(it, l, r) for (int it = l; it < r; ++it)
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double DINF = numeric_limits<double>::infinity();
const ll MOD = 1e9 + 7;
const double EPS = 1e-7;
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
// mt19937 mmtw_(MOD);
// uniform_int_distribution<ll> rd_;
// ll randomll() { return rd_(mmtw_);}
// ll rnd(ll x, ll y) { return rd_(mmtw_) % (y - x + 1) + x; }
// template <class T> T fact(T n) { if (n == 1) return 1; return n * fact(n - 1); }
////////////////////////////////////////////////////////////////////////////////////////////////

int n, m, k;
ll res = 0;
map<int, int> rcnt, rval;
map<int, int> ccnt, cval;
map<pair<int, int>, int> rooks;

void add(int r, int c, int a) {
    res -= (n - ccnt[rval[r]]);
    res -= (n - rcnt[cval[c]]);
    if (rval[r] != cval[c]) res++;

    // cout << res << endl;

    rcnt[rval[r]]--;
    rval[r] ^= a;
    rcnt[rval[r]]++;

    ccnt[cval[c]]--;
    cval[c] ^= a;
    ccnt[cval[c]]++;

    res += (n - ccnt[rval[r]]);
    res += (n - rcnt[cval[c]]);
    if (rval[r] != cval[c]) res--;
    rooks[make_pair(r, c)] ^= a;
}

int main() {
    FAST_IO;
    cin >> n >> m >> k;
    rcnt[0] = n; ccnt[0] = n;
    rep(i, m) {
        // cout << "--- " << i << " ---" << endl;
        int x, y, a;
        cin >> x >> y >> a;
        add(x - 1, y - 1, a);
        rooks[make_pair(x - 1, y - 1)] = a;
    }

    // cout << res << endl;

    rep(i, k) {
        // cout << "--- " << i << " ---" << '\n';
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--; y1--; x2--; y2--;

        int val = rooks[make_pair(x1, y1)];
        add(x1, y1, val);
        add(x2, y2, val);

        cout << res << '\n';
    }
}

Subtask #1
102.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 556 KB Output is correct
4 Correct 3 ms 556 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 234 ms 5608 KB Output is correct
7 Correct 159 ms 5608 KB Output is correct
8 Correct 122 ms 5608 KB Output is correct
9 Correct 126 ms 5608 KB Output is correct
10 Correct 168 ms 5608 KB Output is correct
11 Correct 1909 ms 33984 KB Output is correct
12 Correct 1849 ms 33984 KB Output is correct
13 Execution timed out 2001 ms 34032 KB Time limit exceeded
14 Execution timed out 2060 ms 34032 KB Time limit exceeded
15 Correct 1948 ms 34032 KB Output is correct
16 Correct 1871 ms 34032 KB Output is correct
17 Correct 1951 ms 34032 KB Output is correct
18 Correct 1851 ms 34032 KB Output is correct
19 Execution timed out 2060 ms 34032 KB Time limit exceeded
20 Correct 1889 ms 34032 KB Output is correct