oj.uz

Submission #251717

# Submission time Handle Problem Language Result Execution time Memory
251717 2020-07-22T08:42:58 Z ne4eHbKa Topovi (COCI15_topovi) C++17
120 / 120
 1084 ms 34064 KB 
//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

//const ld pi = arg(complex<ld>(-1, 0));
//const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e5 + 5;

int n, k, p;
ll ans;
map<pii, int> r;
map<int, int> x, y, px, py;

template<typename t>
void change(t &a, t &b, int i, int v) {
    ans += v * (n - b[i]);
    a[i] += v;
}

void row(int i, int v) {
    ifn(v) re;
    change(px, py, x[i], -1);
    x[i] ^= v;
    change(px, py, x[i], +1);
}

void col(int i, int v) {
    ifn(v) re;
    change(py, px, y[i], -1);
    y[i] ^= v;
    change(py, px, y[i], +1);
}

void solve() {
#ifdef _LOCAL
    x.clear();
    y.clear();
    px.clear();
    py.clear();
    r.clear();
#endif // _LOCAL
    cin >> n >> k >> p;
    px[0] = n, py[0] = n;
    fo(k) {
        int x, y;
        cin >> x >> y;
        cin >> r[{x - 1, y - 1}];
    }
    ans = 0;
    for(const auto &i : r) {
        row(i.ft.ft, i.sd);
        col(i.ft.sd, i.sd);
    }
    fo(p) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1, --x2, --y1, --y2;
        int v = r[{x2, y2}] = r[{x1, y1}];
        if(x1 != x2) {
            row(x1, v);
            row(x2, v);
        }
        if(y1 != y2) {
            col(y1, v);
            col(y2, v);
        }
        cout << ans << '\n';
    }
}

int main() {
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message

topovi.cpp: In function 'int m_bpow(ll, ll)':
topovi.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 90 ms 5624 KB Output is correct
7 Correct 67 ms 5112 KB Output is correct
8 Correct 55 ms 4216 KB Output is correct
9 Correct 57 ms 4344 KB Output is correct
10 Correct 60 ms 4472 KB Output is correct
11 Correct 1084 ms 33912 KB Output is correct
12 Correct 924 ms 33872 KB Output is correct
13 Correct 867 ms 33972 KB Output is correct
14 Correct 957 ms 33916 KB Output is correct
15 Correct 955 ms 33912 KB Output is correct
16 Correct 880 ms 33844 KB Output is correct
17 Correct 988 ms 33960 KB Output is correct
18 Correct 920 ms 34040 KB Output is correct
19 Correct 853 ms 34064 KB Output is correct
20 Correct 1028 ms 33912 KB Output is correct