Submission #59183695

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define inf 0x3f3f3f3f
#define pi pair<long long int,long long int>
#define gcd(x,y) __gcd( x, y)
#define ALL(x) x.begin(),x.end()
#define pll pair<long long,long long>
#define debug(x) cerr<<#x<<':'<<x<<endl
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define MP make_pair
#define inf 0x3f3f3f3f
#define pi pair<long long int,long long int>
#define gcd(x,y) __gcd( x, y)
#define ALL(x) x.begin(),x.end()
#define pll pair<long long,long long>
#define debug(x) cerr<<#x<<':'<<x<<endl
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define INTMAX 2147483647
#define INT_MAX LONG_LONG_MAX
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set_ll;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset_ll;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

ll countSafeSquares(ll n, vector<pll>& queens) {
    if(queens.empty()) return n * n;
    set<ll> rows, cols, d1, d2; 
    for(auto [r, c] : queens) {
        rows.insert(r);
        cols.insert(c);
        d1.insert(r + c);
        d2.insert(r - c);
    }
    ll attacked = 0;
    ll row_attacks = rows.size() * n, col_attacks = cols.size() * n;
    attacked = row_attacks + col_attacks - (rows.size() * cols.size());
    for(ll sum : d1) {
        ll from = max(0LL, sum - (n-1));
        ll to = min(n-1, sum); 
        ll len = to - from + 1;
        if(len > 0) {
            ll new_attacks = len;
            for(ll r = from; r <= to; r++) {
                ll c = sum - r;
                if(rows.count(r) || cols.count(c)) new_attacks--;
            }
            attacked += new_attacks;
        }
    }
    for(ll diff : d2) {
        ll from = max(0LL, diff);
        ll to = min(n-1, n-1 + diff);
        ll len = to - from + 1;
        if(len > 0) {
            ll new_attacks = len;
            for(ll r = from; r <= to; r++) {
                ll c = r - diff;
                if(rows.count(r) || cols.count(c) || d1.count(r + c)) new_attacks--;
            }
            attacked += new_attacks;
        }
    }
    return n * n - attacked;
}

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<pll> queens;
    rep(i, 0, q) {
        ll r, c;
        cin >> r >> c;
        r--; c--;
        queens.pb({r, c});
    }
    cout << countSafeSquares(n, queens) << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll tc = 1; //cin >> tc;
    rep(t, 0, tc) {
        solve();
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp:25: warning: "INT_MAX" redefined
   25 | #define INT_MAX LONG_LONG_MAX
      | 
In file included from /usr/include/c++/12/climits:42,
                 from /usr/include/x86_64-linux-gnu/c++/12/bits/stdc++.h:39,
                 from Main.cpp:1:
/usr/lib/gcc/x86_64-linux-gnu/12/include/limits.h:120: note: this is the location of the previous definition
  120 | #define INT_MAX __INT_MAX__
      | 

Judge Result