oj.uz

Submission #602644

# Submission time Handle Problem Language Result Execution time Memory
602644 2022-07-23T09:45:46 Z KhoaHo Topovi (COCI15_topovi) C++17
120 / 120
 436 ms 28972 KB 
/// 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

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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 47 ms 4472 KB Output is correct
7 Correct 41 ms 3920 KB Output is correct
8 Correct 47 ms 3252 KB Output is correct
9 Correct 31 ms 3236 KB Output is correct
10 Correct 33 ms 3464 KB Output is correct
11 Correct 431 ms 28972 KB Output is correct
12 Correct 396 ms 28928 KB Output is correct
13 Correct 408 ms 28868 KB Output is correct
14 Correct 420 ms 28940 KB Output is correct
15 Correct 398 ms 28800 KB Output is correct
16 Correct 409 ms 28956 KB Output is correct
17 Correct 436 ms 28808 KB Output is correct
18 Correct 402 ms 28912 KB Output is correct
19 Correct 395 ms 28912 KB Output is correct
20 Correct 432 ms 28824 KB Output is correct