Submission #925187

#TimeUsernameProblemLanguageResultExecution timeMemory
925187poppy1238New Home (APIO18_new_home)C++17
0 / 100
2928 ms1048576 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/priority_queue.hpp> #ifndef LOCAL/* #pragma GCC optimize("Ofast") #pragma GCC optimize "unroll-loops" #pragma GCC target "mmx,sse,sse2,sse3,sse4,avx,avx2,fma,abm,popcnt,tune=native" //*/ //#pragma GCC optimize "prefetch-loop-arrays" #endif // LOCAL using namespace std; using namespace __gnu_pbds; #define foru(i,a,b) for(ll i=(a);i<(b);i++) #define ford(i,a,b) for(ll i=(a)-1;i>=(b);i--) #define fori(a,b) foru(i,a,b) #define forj(a,b) foru(j,a,b) #define fork(a,b) foru(k,a,b) #define seto(x,i) memset(x,i,sizeof x) #define pf first #define ps second #define pb push_back #define eb emplace_back #define em emplace #define mp make_pair #define mt make_tuple #define popcount __builtin_popcount #define popcountll __builtin_popcountll #define clz __builtin_clz #define clzll __builtin_clzll #define ctz __builtin_ctz #define ctzll __builtin_ctzll #define P2(x) (1LL<<(x)) #define sz(x) (ll)x.size() #define all(x) begin(x),end(x) #define lwb lower_bound #define upb upper_bound #if __SIZEOF_INT128__ typedef __int128_t i128; typedef __uint128_t ui128; #endif typedef int64_t ll; typedef uint64_t ull; typedef long double lld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<lld,lld> pdd; template<class T1,class T2> using ordered_map=tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>; template<class T1> using ordered_set=ordered_map<T1,null_type>; template<class T> using minpq=std::priority_queue<T,vector<T>,greater<T>>; template<class T> using maxpq=std::priority_queue<T,vector<T>,less<T>>; template<class T> using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>; template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>; const int inf=0x3f3f3f3f,MOD=1e9+7; const ll INF=0x3f3f3f3f3f3f3f3f; const lld PI=acos((lld)-1); const ll SEED=443214^chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count(); mt19937 randgen(SEED); ll rand(ll a, ll b){return uniform_int_distribution<ll>(a,b)(randgen);} ll gcd(ll a, ll b){return b?gcd(b,a%b):a;} ll fpow(ll a,ll b){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%MOD;a=a*a%MOD;}return ret;} ll fpow(ll a,ll b,ll M){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%M;a=a*a%M;}return ret;} template<class T1,class T2>constexpr const auto _min(const T1&x,const T2&y){return x<y?x:y;} template<class T,class...Ts>constexpr auto _min(const T&x,const Ts&...xs){return _min(x,_min(xs...));} template<class T1,class T2>constexpr const auto _max(const T1&x,const T2&y){return x>y?x:y;} template<class T,class...Ts>constexpr auto _max(const T&x,const Ts&...xs){return _max(x,_max(xs...));} #define min(...) _min(__VA_ARGS__) #define max(...) _max(__VA_ARGS__) template<class T1,class T2>constexpr bool ckmin(T1&x,const T2&y){return x>y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmin(T&x,const Ts&...xs){return ckmin(x,min(xs...));} template<class T1,class T2>constexpr bool ckmax(T1&x,const T2&y){return x<y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmax(T&x,const Ts&...xs){return ckmax(x,max(xs...));} template<class T1,class T2,class T3,class T4> constexpr const auto operator+(const pair<T1,T2>& a,const pair<T3,T4>& b){return mp(a.pf+b.pf,a.ps+b.ps);} template<class T1,class T2,class T3,class T4> constexpr const auto operator-(const pair<T1,T2>& a,const pair<T3,T4>& b){return mp(a.pf-b.pf,a.ps-b.ps);} template<class T1,class T2,class T3> constexpr const auto operator *(const pair<T1,T2>& a,const T3& b){return mp(a.pf*b,a.ps*b);} template<class T1,class T2,class T3> constexpr const auto operator *(const T1& a,const pair<T2,T3>& b){return b*a;} template<class T1,class T2,class T3> constexpr const auto operator /(const pair<T1,T2>& a,const T3& b){return mp(a.pf/b,a.ps/b);} template<class T1,class T2,class T3,class T4> constexpr const auto& operator+=(pair<T1,T2> &a,const pair<T3,T4> &b){return a=a+b;} template<class T1,class T2,class T3,class T4> constexpr const auto& operator-=(pair<T1,T2> &a,const pair<T3,T4> &b){return a=a-b;} template<class T1,class T2,class T3> constexpr const auto& operator*=(pair<T1,T2> &a,const T3 &b){return a=a*b;} template<class T1,class T2,class T3> constexpr const auto& operator/=(pair<T1,T2> &a,const T3 &b){return a=a/b;} template<class T,class U> void erase(T& t,const U& u){auto it=t.find(u);if(it!=end(t)) t.erase(it);} template<class T> T pop(queue<T> &a){auto b=a.front(); a.pop(); return b;} template<class T> auto pop(T &a){auto b=a.top(); a.pop(); return b;} template<class T> T operator -(vector<T> &a,size_t x){return a[a.size()-x];} template<class T> T operator -(deque<T> &a,size_t x){return a[a.size()-x];} struct chash{ static ll splitmix64(ll x){x+=0x9e3779b97f4a7c15; x=(x^(x>>30))*0xbf58476d1ce4e5b9; x=(x^(x>>27))*0x94d049bb133111eb; return x^(x>>31);} template<class T> size_t operator()(const T &x) const{return splitmix64(hash<T>()(x)+SEED);} template<class T1,class T2> size_t operator()(const pair<T1,T2>&x)const{return 31*operator()(x.first)+operator()(x.second);}}; struct mint { //static constexpr mint rt() { return RT; } // primitive root for FFT int v; explicit operator int() const { return v; } // explicit -> don't silently convert to int mint():v(0) {} mint(ll _v) { v = int((-MOD < _v && _v < MOD) ? _v : _v % MOD); if (v < 0) v += MOD; } bool operator==(const mint& o) const { return v == o.v; } friend bool operator!=(const mint& a, const mint& b) { return !(a == b); } friend bool operator<(const mint& a, const mint& b) { return a.v < b.v; } //friend void re(mint& a) { ll x; re(x); a = mint(x); } //friend string ts(mint a) { return ts(a.v); } mint& operator+=(const mint& o) { if ((v += o.v) >= MOD) v -= MOD; return *this; } mint& operator-=(const mint& o) { if ((v -= o.v) < 0) v += MOD; return *this; } mint& operator*=(const mint& o) { v = int((ll)v*o.v%MOD); return *this; } mint& operator/=(const mint& o) { return (*this) *= inv(o); } friend mint pow(mint a, ll p) { mint ans = 1; assert(p >= 0); for (; p; p /= 2, a *= a) if (p&1) ans *= a; return ans; } friend mint inv(const mint& a) { assert(a.v != 0); return pow(a,MOD-2); } mint operator-() const { return mint(-v); } mint& operator++() { return *this += 1; } mint& operator--() { return *this -= 1; } friend mint operator+(mint a, const mint& b) { return a += b; } friend mint operator-(mint a, const mint& b) { return a -= b; } friend mint operator*(mint a, const mint& b) { return a *= b; } friend mint operator/(mint a, const mint& b) { return a /= b; } friend string to_string(const mint& a){ return to_string(a.v); } friend std::ostream & operator<<(std::ostream & Str, mint const & v) { Str << v.v; return Str; } friend istream& operator>> (istream& stream, mint& v){ stream>>v.v; return stream; } }; template<class T1,class T2> istream& operator>> (istream& stream, pair<T1,T2>& x){stream>>x.pf>>x.ps;return stream;} template<class T> void iin(vector<T> &v,size_t n=0){if(n) v.resize(n);for(auto &i:v) cin>>i;} template<class T> void iin(T *v,size_t n){fori(0,n) cin>>v[i];} void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");} string to_string(char c){return string(1,c);} string to_string(char* s){return (string)s;} string to_string(string s){return s;} template<class T> string to_string(complex<T> c){stringstream ss; ss<<c; return ss.str();} template<class T1,class T2> string to_string(pair<T1,T2> p){return "("+to_string(p.pf)+","+to_string(p.ps)+")";} template<class T1,class T2,class T3> string to_string(tuple<T1,T2,T3> p){auto [a,b,c]=p; return "("+to_string(a)+","+to_string(b)+","+to_string(c)+")";} template<class T1,class T2,class T3,class T4> string to_string(tuple<T1,T2,T3,T4> p){auto [a,b,c,d]=p; return "("+to_string(a)+","+to_string(b)+","+to_string(c)+","+to_string(d)+")";} template<class T> string to_string(T v){string ret="{"; for(const auto& x:v) ret+=to_string(x)+","; return ret+"}";} void DBG(){cerr<<"]"<<endl;} template<class T,class... Ts> void DBG(T x,Ts... xs){cerr<<to_string(x); if(sizeof...(xs)) cerr<<", "; DBG(xs...);} #ifdef LOCAL #define dbg(...) cerr<<"Line("<< __LINE__<<") -> ["<<#__VA_ARGS__<<"]: [", DBG(__VA_ARGS__) #else #define dbg(...) 0 #endif #define nl "\n" void iout(){cout<<nl;} template<class T> void iout(vector<T> v){for(auto i:v) cout<<i<<" "; iout();} template<class T,class... Ts> void iout(T x,Ts... xs){cout<<x; if(sizeof...(xs)) cout<<" "; iout(xs...);} template<class T> void aout(T *v,size_t n){fori(0,n) cout<<v[i]<<" "; iout();} const int N=3e5+10,M=P2(30); ll n,m,q,a,b,c,d,ans[N]; vector<tuple<ll,ll,ll>> store[N]; gp_hash_table<int,vector<tuple<ll,ll,ll,ll>>,chash> echunk; void upd(int lo,int hi,ll t,ll v,ll dir,ll pos,int l=0,int r=M-1,int x=1){ if(hi<l||r<lo) return; if(lo<=l&&r<=hi){ echunk[x].eb(t,v,dir,pos); return; } int mid=l+r>>1; upd(lo,hi,t,v,dir,pos,l,mid,2*x); upd(lo,hi,t,v,dir,pos,mid+1,r,2*x+1); } void updev(ll t,ll x,ll a,ll b){ dbg(t,x,a,b); upd(a,(a+b)/2,t,x,0,a); upd((a+b)/2+1,b,t,x,1,b); } void updstore(ll t,ll x,ll a,ll b,ll c){ updev(t,!x,a,c); updev(t,x,a,b); updev(t,x,b,c); } void rise(int l=0,int r=M-1,int x=1){ if(!sz(echunk[x])){ return; } sort(all(echunk[x])); dbg(l,r,x,echunk[x]); set<ll> s[2]; for(auto [t,v,dir,pos]:echunk[x]){ if(v==0){ erase(s[dir],pos); } else if(v==1){ s[dir].em(pos); } else if(v==inf){ if(sz(s[0])){ ckmax(ans[dir],pos-*begin(s[0])); } if(sz(s[1])){ ckmax(ans[dir],*rbegin(s[1])-pos); } } } int mid=l+r>>1; rise(l,mid,2*x); rise(mid+1,r,2*x+1); } void BRINGER_OF_LIGHT(){ cin>>n>>m>>q; fori(0,n){ cin>>a>>b>>c>>d; store[b].eb(c,1,a); store[b].eb(d,0,a); } fori(1,m+1){ set<ll> s; s.em(-inf); s.em(inf); updev(0,1,-inf,inf); sort(all(store[i])); for(auto [t,a,x]:store[i]){ if(a==1){ s.em(x); updstore(t,a,*prev(s.find(x)),x,*next(s.find(x))); } else{ updstore(t,a,*prev(s.find(x)),x,*next(s.find(x))); erase(s,x); } } } fori(0,q){ cin>>a>>b; ll x=a; for(x+=M;x;x/=2){ echunk[x].eb(b,inf,i,a); } } rise(); fori(0,q){ if(ans[i]>=inf/2){ ans[i]=-1; } cout<<ans[i]<<nl; } } int main(){ cin.tie(0)->sync_with_stdio(0); cout<<fixed<<setprecision(14); #ifdef LOCAL //fin("a.txt"); #endif int T=1; //cin>>T; foru(t,1,T+1){ BRINGER_OF_LIGHT(); } return 0; } /** 4 2 4 3 1 1 10 9 2 2 4 7 2 5 7 4 1 8 10 5 3 5 6 5 9 1 10 */

Compilation message (stderr)

new_home.cpp: In function 'void upd(int, int, ll, ll, ll, ll, int, int, int)':
new_home.cpp:150:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  150 |     int mid=l+r>>1;
      |             ~^~
new_home.cpp: In function 'void updev(ll, ll, ll, ll)':
new_home.cpp:131:22: warning: statement has no effect [-Wunused-value]
  131 |     #define dbg(...) 0
      |                      ^
new_home.cpp:154:5: note: in expansion of macro 'dbg'
  154 |     dbg(t,x,a,b);
      |     ^~~
new_home.cpp: In function 'void rise(int, int, int)':
new_home.cpp:131:22: warning: statement has no effect [-Wunused-value]
  131 |     #define dbg(...) 0
      |                      ^
new_home.cpp:168:5: note: in expansion of macro 'dbg'
  168 |     dbg(l,r,x,echunk[x]);
      |     ^~~
new_home.cpp:186:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  186 |     int mid=l+r>>1;
      |             ~^~
new_home.cpp: In function 'void fin(std::string)':
new_home.cpp:120:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 | void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");}
      |                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
new_home.cpp: In function 'void fout(std::string)':
new_home.cpp:120:78: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 | void fin(string s){freopen(s.c_str(),"r",stdin);} void fout(string s){freopen(s.c_str(),"w",stdout);} void fio(string s){fin(s+".in"); fout(s+".out");}
      |                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...