oj.uz

답안 #64973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
64973 2018-08-06T10:44:25 Z forestryks Topovi (COCI15_topovi) C++14
66 / 120
 2000 ms 66560 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--;
}

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[{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[{x1, y1}];
        add(x1, y1, val);
        add(x2, y2, val);
        rooks[{x1, y1}] = 0;
        rooks[{x2, y2}] = val;

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

Subtask #1
66.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 400 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 3 ms 424 KB Output is correct
6 Correct 229 ms 6416 KB Output is correct
7 Correct 190 ms 6416 KB Output is correct
8 Correct 130 ms 6416 KB Output is correct
9 Correct 145 ms 6608 KB Output is correct
10 Correct 169 ms 7348 KB Output is correct
11 Execution timed out 2033 ms 42712 KB Time limit exceeded
12 Execution timed out 2032 ms 48892 KB Time limit exceeded
13 Correct 2000 ms 54920 KB Output is correct
14 Execution timed out 2063 ms 60780 KB Time limit exceeded
15 Runtime error 1870 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
16 Execution timed out 2078 ms 66560 KB Time limit exceeded
17 Execution timed out 2074 ms 66560 KB Time limit exceeded
18 Execution timed out 2073 ms 66560 KB Time limit exceeded
19 Execution timed out 2001 ms 66560 KB Time limit exceeded
20 Runtime error 1895 ms 66560 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.