Submission #602644

#	Time	Username	Problem	Language	Result	Execution time	Memory
602644		KhoaHo	Topovi (COCI15_topovi)	C++17	120 / 120	436 ms	28972 KiB

topovi

/// KoJa
#include <bits/stdc++.h>
using namespace std;
#define task "topovi"
#define pb push_back
#define SZ(a) (a).begin(), (a).end()
#define SZZ(a, Begin, End) (a) + (Begin), (a) + (Begin) + (End)
#define BIT(a) (1LL << (a))
#define vec vector
#define fi first
#define se second
#define mp make_pair
#define MASK(x, i) (((x) >> i)&1)

typedef long long ll;
typedef pair<int, int> ii;

template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b, 1) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b, 1) : 0); }
void fastio()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    if (fopen(task ".inp", "r"))
    {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    else if (fopen(task ".in", "r"))
    {
        freopen(task ".in", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
}
const int N = int(12e5) + 10;
const ll INF = 1e18;
int n, k, p;
int r[N], c[N];
vec<pair<ii, int>> car;
unordered_map<int, int> xorR, xorC;
map<ii, int> cnt;
struct Query
{
    int x, y, u, v;
    Query(){}
    Query(int _x, int _y, int _u, int _v)
    {
        x = _x;
        y = _y;
        u = _u;
        v = _v;
    }
};
vec<Query> queries;
void init()
{
    cin >> n >> k >> p;
    for(int i = 1; i <= k; i++)
    {
        int x, y, w;
        cin >> x >> y >> w;
        car.pb(mp(ii(x, y), w));
    }
    for(int i = 1; i <= p; i++)
    {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        queries.pb(Query(x, y, u, v));
    }
}
ll ans = 0;
void update(int x, int y, int val)
{
    ans -= n - xorC[r[x]];
    ans -= n - xorR[c[y]];
    if(r[x] != c[y])
        ++ans;

    --xorR[r[x]];
    r[x] ^= val;
    ++xorR[r[x]];

    --xorC[c[y]];
    c[y] ^= val;
    ++xorC[c[y]];

    ans += n - xorC[r[x]];
    ans += n - xorR[c[y]];
    if(r[x] != c[y])
        --ans;

    cnt[mp(x, y)] ^= val;
}
void process(const int &tc)
{
    vec<int> val;
    for(int i = 0; i < k; i++)
    {
        val.pb(car[i].fi.fi);
        val.pb(car[i].fi.se);
    }
    for(int i = 0; i < p; i++)
    {
        val.pb(queries[i].x);
        val.pb(queries[i].y);
        val.pb(queries[i].u);
        val.pb(queries[i].v);
    }
    sort(SZ(val));
    val.erase(unique(SZ(val)), val.end());
    for(int i = 0; i < k; i++)
    {
        car[i].fi.fi = lower_bound(SZ(val), car[i].fi.fi) - val.begin() + 1;
        car[i].fi.se = lower_bound(SZ(val), car[i].fi.se) - val.begin() + 1;
    }
    for(int i = 0; i < p; i++)
    {
        queries[i].x = lower_bound(SZ(val), queries[i].x) - val.begin() + 1;
        queries[i].y = lower_bound(SZ(val), queries[i].y) - val.begin() + 1;
        queries[i].u = lower_bound(SZ(val), queries[i].u) - val.begin() + 1;
        queries[i].v = lower_bound(SZ(val), queries[i].v) - val.begin() + 1;
    }
    xorR[0] = xorC[0] = n;
    for(int i = 0; i < k; i++)
    {
        int x = car[i].fi.fi;
        int y = car[i].fi.se;
        update(x, y, car[i].se);
    }
    for(int i = 0; i < p; i++)
    {
        auto tmp = queries[i];
        int w = cnt[mp(tmp.x, tmp.y)];
        update(tmp.x, tmp.y, w);
        update(tmp.u, tmp.v, w);
        cout << ans << '\n';
    }
}
int main()
{
    fastio();
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        init();
        process(i);
    }
    return 0;
}

Compilation message (stderr)

topovi.cpp: In function 'void fastio()':
topovi.cpp:28:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         freopen(task ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 120 / 120