Submit Info #2603

Problem Lang User Status Time Memory
Rectangle Sum cpp Imperi AC 3160 ms 495.77 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.63 MiB
max_random_00 AC 2746 ms 495.77 MiB
max_random_01 AC 2748 ms 495.68 MiB
max_random_02 AC 2871 ms 495.72 MiB
n_131072_00 AC 1348 ms 324.71 MiB
random_00 AC 1852 ms 316.88 MiB
random_01 AC 2012 ms 373.77 MiB
random_02 AC 1077 ms 133.49 MiB
small_00 AC 10 ms 2.34 MiB
small_01 AC 7 ms 1.17 MiB
small_02 AC 5 ms 0.88 MiB
xy_concentrate_00 AC 2953 ms 495.77 MiB
xy_concentrate_01 AC 3160 ms 495.75 MiB
xy_concentrate_02 AC 3026 ms 495.75 MiB

#include <cassert> #include "limits.h" #include <limits> #include <algorithm> #include <bitset> #include <cctype> #include <cmath> #include <complex> #include <deque> #include <functional> #include <iomanip> #include <iostream> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <unordered_map> #include <vector> #include <random> #include <memory> #include <utility> #define rep(i, a, b) for (long long (i) = (a); i < (b); i++) #define all(i) i.begin(), i.end() #define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) void debug_out(){std::cerr<<std::endl;} template<typename H,typename... T> void debug_out(H head,T... tail){ std::cerr<<" "<<head; debug_out(tail...); } template <typename T1, typename T2> std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) { return os << pa.first << " " << pa.second; } template <typename T> std::ostream& operator<<(std::ostream& os, std::vector<T> vec) { for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " "); return os; } template<typename T1,typename T2> inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);} template<typename T1,typename T2> inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);} long long pow_mod(long long a, long long b, long long mod=-1) { if ((a == 0)||(mod!=-1&&a%mod==0)) { return 0; } long long x = 1; while (b > 0) { if (b & 1) { x = (mod!=-1)?(x * a) % mod:x*a; } a = (mod!=-1)?(a * a) % mod:a*a; b >>= 1; } return x; } const long long MOD = 998244353; // const long long MOD = 1e9 + 7; using ll = long long; using P = std::pair<long long,long long>; //永続動的セグ木 template<typename T> class PersistentSegmentTree{ private: using F=std::function<T(T,T)>; long long n,n0; F fn; T init; class Node{ public: std::shared_ptr<Node> left,right; std::weak_ptr<Node> par; T value; Node(T i,const std::shared_ptr<Node>& par_):value(i),left(),right(),par(par_){} Node(T i,std::shared_ptr<Node>& par_):value(i),left(),right(),par(std::move(par_)){} Node(T i):value(i),left(),right(),par(){} }; std::shared_ptr<Node> root; T query(long long a,long long b,const std::shared_ptr<Node>& now,long long l,long long r){ if(a<=l&&r<=b){ return now->value; } if(b<=l||r<=a){ return init; } T lval=(now->left)?query(a,b,now->left,l,l+(r-l)/2):init; T rval=(now->right)?query(a,b,now->right,l+(r-l)/2,r):init; return fn(lval,rval); } public: //要素数の最大値n,単位元i,演算fを渡す PersistentSegmentTree(long long n_,T i,F f):n(n_),init(i),fn(f),root(new Node(init)){ n0=1; while(n0<n_)n0<<=1; } PersistentSegmentTree(const std::shared_ptr<Node>& root_,long long n_,T i,F f):n(n_),init(i),fn(f),root(root_){ n0=1; while(n0<n_)n0<<=1; } PersistentSegmentTree():root(){} // 更新 Ai=fn(Ai,val) を行う,dest=trueのときは初期化 PersistentSegmentTree update(long long i,T val,bool dest){ assert(0<=i&&i<n); std::shared_ptr<Node> now(root); std::shared_ptr<Node> nr=std::make_shared<Node>(init),root_(nr); long long l=0,r=n0; bool isok=true; while(r-l>1){ long long mid=l+(r-l)/2; if(i<mid){ if(isok&&now->right)nr->right=now->right; nr->left=std::make_shared<Node>(init,nr); if(isok){ if(!now->left)isok=false; else now=now->left; } nr=nr->left; r=mid; }else{ if(isok&&now->left)nr->left=now->left; nr->right=std::make_shared<Node>(init,nr); if(isok){ if(!now->right)isok=false; else now=now->right; } nr=nr->right; l=mid; } } if(dest)nr->value=val; else nr->value=fn((isok)?now->value:init,val); while(nr->par.lock()){ nr=nr->par.lock(); nr->value=fn((nr->left)?nr->left->value:init,(nr->right)?nr->right->value:init); } return PersistentSegmentTree(nr,n,init,fn); } //[a,b)の区間演算結果を返す T query(long long a,long long b){ assert(0<=a&&b<=n); return query(a,b,root,0,n0); } }; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); ll n,q; std::cin>>n>>q; std::vector<PersistentSegmentTree<ll>> seg(n+1); seg[n]=PersistentSegmentTree<ll>((ll)(1e9+10),0,[](ll a,ll b){return a+b;}); struct Point{ ll x,y,w; Point(ll a,ll b,ll c):x(a),y(b),w(c){} }; std::vector<Point> points(n,Point(-1,-1,-1)); rep(i,0,n)std::cin>>points[i].x>>points[i].y>>points[i].w; auto comp=[](const Point& a,const Point& b)->bool{return a.x<b.x;}; std::sort(all(points),comp); for(ll i=n-1;i>=0;i--)seg[i]=seg[i+1].update(points[i].y,points[i].w,false); rep(i,0,q){ ll l,d,r,u; std::cin>>l>>d>>r>>u; ll ans=0; ans+=seg[std::lower_bound(all(points),Point(l,-1,-1),comp)-points.begin()].query(d,u); ans-=seg[std::lower_bound(all(points),Point(r,-1,-1),comp)-points.begin()].query(d,u); std::cout<<ans<<"\n"; } return 0; }