結果
問題 | No.1920 Territory |
ユーザー |
![]() |
提出日時 | 2022-04-17 01:13:05 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 596 ms / 5,000 ms |
コード長 | 10,169 bytes |
コンパイル時間 | 2,690 ms |
コンパイル使用メモリ | 214,972 KB |
実行使用メモリ | 44,228 KB |
最終ジャッジ日時 | 2024-06-28 15:49:59 |
合計ジャッジ時間 | 15,383 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:303:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 303 | for(auto[a,b,c]:y_perm){ | ^ main.cpp:319:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 319 | for(auto[a,b,c]:y_perm){ | ^ main.cpp:359:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 359 | auto[l,r] = *itr3; | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i,n) for(int i=0;i<n;i++)#define rrep(i,n) for(int i=n-1;i>=0;i--)#define rrep2(i,n,k) for(int i=n-1;i>=n-k;i--)#define vll(n,i) vector<long long>(n,i)#define v2ll(n,m,i) vector<vector<long long>>(n,vll(m,i))#define v3ll(n,m,k,i) vector<vector<vector<long long>>>(n,v2ll(m,k,i))#define v4ll(n,m,k,l,i) vector<vector<vector<vector<long long>>>>(n,v3ll(m,k,l,i))#define all(v) v.begin(),v.end()#define chmin(k,m) k = min(k,m)#define chmax(k,m) k = max(k,m)#define Pr pair<ll,ll>#define Tp tuple<ll,ll,ll>#define riano_ std::ios::sync_with_stdio(false);std::cin.tie(nullptr)#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")//Graphstruct graph {long long N;vector<vector<tuple<long long,long long,int>>> G;vector<long long> par_v;vector<long long> par_e;int edge_count = 0;graph(long long n) {N = n;G = vector<vector<tuple<long long,long long,int>>>(N);par_v = vector<long long>(N,-1);par_e = vector<long long>(N,-1);}void unite(long long a,long long b,long long cost = 1,bool directed = false){G[a].emplace_back(b,cost,edge_count);if(!directed) G[b].emplace_back(a,cost,edge_count);edge_count++;}};//map addtemplate <typename T>void add(map<T,ll> &cnt,T a,ll n = 1){if(cnt.count(a)) cnt[a] += n;else cnt[a] = n;}const ll mod = 998244353;template<uint64_t mod>struct modint{uint64_t val;constexpr modint(const int64_t val_=0) noexcept:val((val_%int64_t(mod)+int64_t(mod))%int64_t(mod)){}constexpr modint operator-() const noexcept{return modint(*this)=mod-val;}constexpr modint operator+(const modint rhs) const noexcept{return modint(*this)+=rhs;}constexpr modint operator-(const modint rhs) const noexcept{return modint(*this)-=rhs;}constexpr modint operator*(const modint rhs) const noexcept{return modint(*this)*=rhs;}constexpr modint operator/(const modint rhs) const noexcept{return modint(*this)/=rhs;}constexpr modint &operator+=(const modint rhs) noexcept{val+=rhs.val;val-=((val>=mod)?mod:0);return (*this);}constexpr modint &operator-=(const modint rhs) noexcept{val+=((val<rhs.val)?mod:0);val-=rhs.val;return (*this);}constexpr modint &operator*=(const modint rhs) noexcept{val=val*rhs.val%mod;return (*this);}constexpr modint &operator/=(modint rhs) noexcept{uint64_t ex=mod-2;modint now=1;while(ex){now*=((ex&1)?rhs:1);rhs*=rhs,ex>>=1;}return (*this)*=now;}modint & operator++(){val++;if (val == mod) val = 0;return *this;}modint operator++(int){modint<mod> res = *this;++*this;return res;}constexpr bool operator==(const modint rhs) noexcept{return val==rhs.val;}constexpr bool operator!=(const modint rhs) noexcept{return val!=rhs.val;}friend constexpr ostream &operator<<(ostream& os,const modint x) noexcept{return os<<(x.val);}friend constexpr istream &operator>>(istream& is,modint& x) noexcept{uint64_t t;is>>t,x=t;return is;}};typedef modint<mod> mint;mint pw(long long a,long long b,long long m = mod){if(a%m==0) return mint(0);if(b==0) return mint(1);else if(b%2==0){long long x = pw(a,b/2,m).val;return mint(x*x);}else{long long x = pw(a,b-1,m).val;return mint(a*x);}}mint modinv(long long a, long long m = mod) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;return mint(u);}#define vm(n,i) vector<mint>(n,i)#define v2m(n,m,i) vector<vector<mint>>(n,vm(m,i))#define v3m(n,m,k,i) vector<vector<vector<mint>>>(n,v2m(m,k,i))#define v4m(n,m,k,l,i) vector<vector<vector<vector<mint>>>>(n,v3m(m,k,l,i))void out(vector<ll> &v){for(ll x:v) cout << x << " ";cout << "\n"; return;}//segment tree//1-indexed allclass segtree {public:ll n;vector<ll> A;segtree(ll k){n = 1;while(n<k){ n *= 2; }A=vector<ll>(2*n,0);}//a[i]にxを加算するvoid add(ll i,ll x){int index = n-1+i;A[index] += x;while(index>1){index /= 2;A[index] = A[2*index]+A[2*index+1];}}//a[i]をにするvoid replace(ll i,ll x){int index = n-1+i;A[index] = x;while(index>1){index /= 2;A[index] = A[2*index]+A[2*index+1];}}//a[i]+a[i+1]+…+a[j]を求めるll sum(ll i,ll j){return rangesum(i,j,1,1,n);}// a,b求める区間 k区間番号 c,d区間の始終点(k=1,c=1,d=nで入力する)ll rangesum(ll a,ll b,ll k,ll c,ll d){//単位元の設定ll el = 0;if(d<a||b<c){return el;}else if(a<=c&&d<=b){return A[k];}else{//2区間に分割して演算を行うll p = rangesum(a,b,k*2,c,(c+d)/2)+rangesum(a,b,k*2+1,(c+d)/2+1,d);return p;}}};//Unionfind//size>4e5 の時はvが足りなくなるので注意struct unionfind {//自身が親であれば、その集合に属する頂点数に-1を掛けたもの//そうでなければ親のidvector<long long> r;vector<bool> lp;vector<long long> cnt;vector<long long> repr;vector<long long> per;unionfind(long long N,vector<long long> v=vector<long long>(4e5+2,0)) { //vで代表点の優先順位をinputr = vector<long long>(N, -1);lp = vector<bool>(N,false);cnt = vector<long long>(N, 0);repr = vector<long long>(N, -1);rep(i,N) repr[i] = i;per = v;}long long root(long long x) {if (r[x] < 0) return x;return r[x] = root(r[x]);}bool unite(long long x, long long y) {x = root(x);y = root(y);if (x == y){lp[x] = true;return false;}long long tmp = 0;if (r[x] > r[y]) swap(x, y);tmp = repr[x];if(per[repr[x]]>per[repr[y]]){tmp = repr[y];}r[x] += r[y];cnt[x] += cnt[y];r[y] = x;repr[x] = tmp;lp[x] = (lp[x]||lp[y]);return true;}long long size(long long x) {return max(-r[root(x)],0LL);}long long count(long long x){return cnt[root(x)];}long long represent(long long x){return repr[root(x)];}// 2つのデータx, yが属する木が同じならtrueを返すbool same(long long x, long long y) {long long rx = root(x);long long ry = root(y);return rx == ry;}//閉路の存在判定bool loop(ll x){return lp[root(x)];}//重みをつける場合void eval(ll i,ll x){cnt[i] = x;}void eval_add(ll i,ll x = 1){cnt[i] += x;}};int main(){riano_; ll ans = 0;ll N,M,K,H,W,Q,L,R,T,C,A,B;cin >> N >> M;ans -= (N+M);//main関数内でsegtree seq(2e5+1);//などと宣言し seq.replace(i,x);//のように使う 1-indexed 注意!!!!!!vector<Tp> y_perm;set<ll> tate;rep(i,N){ll a,b,c; cin >> a >> b >> c;y_perm.emplace_back(a,b,c);}rep(i,M){ll p,q,r; cin >> p >> q >> r;y_perm.emplace_back(q,-1,p);y_perm.emplace_back(r,1e9,p);tate.insert(p);}sort(all(y_perm));for(auto[a,b,c]:y_perm){if(b==-1){seq.add(c,1);}else if(b==1e9){seq.add(c,-1);}else{ans += seq.sum(b,c);}}//main関数内でunionfind uf(2e5+1);set<Pr> s; s.insert(make_pair(1e9,1e9)); s.insert(make_pair(0,0));set<ll> num; num.insert(0); num.insert(1e9);for(auto[a,b,c]:y_perm){if(b==-1){auto itr = s.lower_bound(make_pair(c,1e9)); itr--;if((*itr).second>c){ll k,l;auto itr2 = num.lower_bound(c); k = *itr2;itr2--; l = *itr2;ll n = (*itr).first,m = (*itr).second;s.erase(itr);s.insert(make_pair(n,l)); s.insert(make_pair(k,m));}s.insert(make_pair(c,c));num.insert(c);}else if(b==1e9){auto itr = s.lower_bound(make_pair(c,1e9)); itr--;num.erase(c);if((*itr).second>=c){ll k,l;auto itr2 = num.lower_bound(c); k = *itr2;itr2--; l = *itr2;ll n = (*itr).first,m = (*itr).second;s.erase(itr);if(n!=c) s.insert(make_pair(n,l));if(m!=c) s.insert(make_pair(k,m));}}else{auto itr = num.lower_bound(b);auto itr2 = num.lower_bound(c+1);if(itr==itr2){ans++; continue;}set<Pr> er_list;auto itr3 = s.lower_bound(make_pair(b,1e9));itr3--;if((*itr3).second<b) itr3++;auto itr4 = s.lower_bound(make_pair(c,1e9));L = 1e9; R = 0;while(itr3!=itr4){auto[l,r] = *itr3;er_list.insert(*itr3);chmin(L,l); chmax(R,r);itr3++;uf.unite(L,l);}for(auto p:er_list){s.erase(p);}s.insert(make_pair(L,R));}}rep(i,2e5+1){if(tate.count(i)&&uf.root(i)==i){ans++;//cout << i << " ";}}//cout << endl;cout << ans << endl;}