oj.uz

Submission #100820

# Submission time Handle Problem Language Result Execution time Memory
100820 2019-03-14T16:49:50 Z MohamedAhmed0 Topovi (COCI15_topovi) C++14
120 / 120
 822 ms 29384 KB 
#include <bits/stdc++.h>

using namespace std;

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);
    }
};

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    size_t ans=0;
    for(int i=0;i<x.first;i++)
      ans+=x.second;
    return ans;
  }
};

unordered_map< pair<int,  int> , long long , HASH> mp ;
unordered_map<int , long long>rows , columns ;
unordered_map<int , long long>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:60: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:66: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:73: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 2 ms 256 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 81 ms 5148 KB Output is correct
7 Correct 67 ms 4828 KB Output is correct
8 Correct 44 ms 3576 KB Output is correct
9 Correct 50 ms 3628 KB Output is correct
10 Correct 61 ms 3704 KB Output is correct
11 Correct 708 ms 29372 KB Output is correct
12 Correct 734 ms 29248 KB Output is correct
13 Correct 729 ms 29308 KB Output is correct
14 Correct 714 ms 29248 KB Output is correct
15 Correct 716 ms 29324 KB Output is correct
16 Correct 741 ms 29360 KB Output is correct
17 Correct 735 ms 29384 KB Output is correct
18 Correct 776 ms 29244 KB Output is correct
19 Correct 822 ms 29248 KB Output is correct
20 Correct 810 ms 29368 KB Output is correct