oj.uz

Submission #100821

# Submission time Handle Problem Language Result Execution time Memory
100821 2019-03-14T16:58:59 Z MohamedAhmed0 Topovi (COCI15_topovi) C++14
120 / 120
 384 ms 45380 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

struct chash {
    int operator()(pair<int , int> x) const { return x.first* 31 + x.second; }
};

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

gp_hash_table< pair<int,  int> , long long , chash> mp ;
gp_hash_table<int , long long , custom_hash>rows , columns ;
gp_hash_table<int , long long , custom_hash>rowcnt , columncnt ;

long long n , k , p ;

long long ans = 0ll ;

void update(int r , int c , int x)
{
    ans -= (n - rowcnt[columns[c]]) ;
    ans -= (n - columncnt[rows[r]]) ;
    //handle double counting
    if(rows[r] == columns[c])
        ans++ ;
    rowcnt[rows[r]]-- ;
    rows[r] ^= x ;
    rowcnt[rows[r]]++;
    columncnt[columns[c]]-- ;
    columns[c] ^= x ;
    columncnt[columns[c]]++ ;
    ans += (n - rowcnt[columns[c]]) ;
    ans += (n - columncnt[rows[r]]) ;
    //handle double counting
    if(rows[r] == columns[c])
        ans-- ;
    return ;
}

int main()
{
    scanf("%lld %lld %lld" , &n , &k , &p) ;
    rowcnt[0] = columncnt[0] = n ;
    for(int i = 0 ; i < k ; ++i)
    {
        int a , b ;
        long long c ;
        scanf("%d %d %lld" , &a , &b , &c) ;
        mp[{a , b}] = c ;
        update(a , b , c) ;
    }
    while(p--)
    {
        int a , b , c , d ;
        scanf("%d %d %d %d" , &a , &b , &c , &d) ;
        int x = mp[{a , b}] ;
        update(a , b , x) ;
        update(c , d , x) ;
        mp[{c , d}] = x ;
        printf("%lld\n" , ans) ;
    }
    return 0 ;
}

Compilation message

topovi.cpp: In function 'int main()':
topovi.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld %lld" , &n , &k , &p) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %lld" , &a , &b , &c) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
topovi.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d" , &a , &b , &c , &d) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 48 ms 6024 KB Output is correct
7 Correct 42 ms 5936 KB Output is correct
8 Correct 37 ms 6060 KB Output is correct
9 Correct 37 ms 5916 KB Output is correct
10 Correct 57 ms 5916 KB Output is correct
11 Correct 384 ms 45120 KB Output is correct
12 Correct 366 ms 45332 KB Output is correct
13 Correct 364 ms 45220 KB Output is correct
14 Correct 331 ms 45084 KB Output is correct
15 Correct 363 ms 45124 KB Output is correct
16 Correct 336 ms 45280 KB Output is correct
17 Correct 381 ms 45380 KB Output is correct
18 Correct 355 ms 45112 KB Output is correct
19 Correct 353 ms 45244 KB Output is correct
20 Correct 352 ms 45260 KB Output is correct