oj.uz

Submission #100819

# Submission time Handle Problem Language Result Execution time Memory
100819 2019-03-14T16:48:35 Z MohamedAhmed0 Topovi (COCI15_topovi) C++14
120 / 120
 896 ms 35752 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 , custom_hash>rows , columns ;
unordered_map<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: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 2 ms 256 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 120 ms 6152 KB Output is correct
7 Correct 99 ms 5636 KB Output is correct
8 Correct 67 ms 4216 KB Output is correct
9 Correct 69 ms 4344 KB Output is correct
10 Correct 78 ms 4472 KB Output is correct
11 Correct 839 ms 35588 KB Output is correct
12 Correct 808 ms 35584 KB Output is correct
13 Correct 820 ms 35700 KB Output is correct
14 Correct 845 ms 35556 KB Output is correct
15 Correct 896 ms 35644 KB Output is correct
16 Correct 859 ms 35520 KB Output is correct
17 Correct 851 ms 35652 KB Output is correct
18 Correct 819 ms 35548 KB Output is correct
19 Correct 823 ms 35640 KB Output is correct
20 Correct 846 ms 35752 KB Output is correct