#include <bits/stdc++.h>
#include <bits/extc++.h>
//#include <atcoder/all>
//#define double long double
#define int ll
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);
#define pb push_back
#define UNIQUE(a) sort(ALL(a));a.resize(unique(ALL(a))-a.begin());
#define ALL(X) X.begin(),X.end()
#define F(i,n) FF(i,0,n)
#define F1(i,n) FF(i,1,n+1)
#define FF(i,n,m) for(int i=(int)n;i<int(m);++i)
#define rF(i,a,b) for(int i=a;i>=(int)b;--i)
#define mkp(a,b) make_pair(a,b)
#define Fi first
#define Se second
//#pragma GCC optimize("Ofast")//,unroll-loops
//#pragma GCC target("popcnt")
using namespace std;
using ll=long long;
using ull=unsigned long long;
using int128= __int128_t;
using uint128= __uint128_t;
using pii =pair<int,int> ;
const double pi=acos(-1);
template<typename T> inline bool remax(T& a, const T b) {return b>a?a=b,1:0;}
template<typename T> inline bool remin(T& a, const T b) {return b<a?a=b,1:0;}
inline ostream& operator << (ostream& os,__int128_t a){if(a==0) {return (os<<'0');}bool flag=0;if(a<0) {a=-a,flag=1;}string s;while(a){s+=a%10+'0';a/=10;}s+=flag?"-":"";reverse(ALL(s));return os<<s;}
inline istream& operator >>(istream& is,__int128_t& a){string s;cin>>s;a=0;bool flag=0;for(auto c:s){if(c=='-') flag=1;else a=a*__int128_t(10)+__int128_t(c-'0');} if(flag) a*=-1;return is;}
template<typename T,typename P> inline ostream& operator << (ostream& os,pair<T,P> a){os<<a.first<<" "<<a.second; return os;}
template<typename T,typename P> inline istream& operator >> (istream& is,pair<T,P> &a){is>>a.first>>a.second; return is;}
template <typename T> void clear(T& a){T b;swap(a,b);return;}
template <typename T> inline ostream& operator <<(ostream& os,vector<T>& t){for(auto& x:t){os<<x<<' ';}os<<'\n';return os;}
template <typename T,size_t N> inline ostream& operator <<(ostream& os,array<T,N>& t){for(auto& x:t){os<<x<<' ';}os<<'\n';return os;}
template <typename T> inline ostream& operator <<(ostream& os,set<T>& t){for(auto& x:t){os<<x<<' ';}os<<'\n';return os;}
template <typename T,typename P> inline ostream& operator <<(ostream& os,map<T,P>& t){for(auto& [l,r]:t){os<<l<<"|"<<r<<'\n';}return os;}
template<typename T>using rbtree =__gnu_pbds::tree<T,__gnu_pbds::null_type,less<T>,__gnu_pbds::rb_tree_tag,__gnu_pbds::tree_order_statistics_node_update>;
template<typename T,typename P=less<T>> using PQ=__gnu_pbds::priority_queue<T,P,__gnu_pbds::pairing_heap_tag>;
template <int mod>struct Modint{
int val;
inline Modint(int _val=0){val=_val%mod;if(val<0) val+=mod;}
inline Modint operator +(const Modint& o) const {Modint res;res.val=val+o.val;if(res.val>=mod){res.val-=mod;} return res;}
inline Modint operator +(const int& o) const {return Modint(val+o);}
inline Modint operator -() const {Modint res;res.val=-val;if(res.val<0) {res.val+=mod;}return res;}
inline Modint operator -(const Modint& o) const {Modint res;res.val=val-o.val;if(res.val<0) {res.val+=mod;}return res;}
inline Modint operator -(const int& o) const {return Modint(val-o);}
inline Modint operator *(const Modint& o) const {return Modint(val*o.val);}
inline Modint operator *(const int& o) const {return Modint(val*(o%mod));}
inline Modint operator +=(const Modint& o){*this=(*this)+o;return *this;}
inline Modint operator -=(const Modint& o){*this=(*this)-o;return *this;}
inline Modint operator *=(const Modint& o){*this=(*this)*o;return *this;}
inline Modint Pow(int b) const {Modint tmp(val),ret(1);while(b){if(b&1){ret*=tmp;}b>>=1;tmp*=tmp;}return ret;}
inline Modint Pow(const Modint& a, int b) const {return a.Pow(b);}
inline Modint inv() const {return (*this).Pow(mod-2);}
inline Modint operator /(const Modint& o) const {return *this*o.inv();}
inline Modint operator /(const int& o) const {return *this*Modint(o).inv();}
inline bool operator ==(const Modint& o) const {return val==o.val;}
inline friend ostream& operator << (ostream& o, Modint<mod> x){return o << x.val;}
inline friend Modint<mod> operator +(const int& x, const Modint<mod>& y){return Modint<mod>(x+y.val);}
inline friend Modint<mod> operator -(const int& x, const Modint<mod>& y){return Modint<mod>(x-y.val);}
inline friend Modint<mod> operator *(const int& x, const Modint<mod>& y){return Modint<mod>(x%mod*y.val);}
};
using mint998244353=Modint<998244353>;
using mint1000000007=Modint<1000000007>;
const int N=2E5+5;
const ll M=105;
const ll INF_64=0x3f3f3f3f3f3f3f3f;
const int INF_32=0x3f3f3f3f;
const int16_t INF_16=0x3f3f;
const int klog=20;
const int mod=1000000007;//1000000007;//998244353
const double eps=1E-5;
using mint=mint998244353;
void gen(){
}
template<class T>
struct BIT2D{
static const int kN=2000+5,kM=2000+5;
int n,m;
int lowbit(int x){return x&(-x);}
T C[kN][kM];
void init(int _n,int _m){
n=_n+3;
m=_m+3;
memset(C,0,sizeof(C));
}
void add(int x,int y,T val){
for(int i=x;i<=n;i+=lowbit(i))
for(int j=y;j<=m;j+=lowbit(j))
C[i][j]+=val;
}
T ask(int x,int y){
T re=0;
for(int i=x;i>0;i-=lowbit(i))
for(int j=y;j>0;j-=lowbit(j))
re+=C[i][j];
return re;
}
};
BIT2D<int> bit;
void sol() {
int n,m;cin>>n>>m;
bit.init(n,n);
F(i,m){
int a,b;cin>>a>>b;
bit.add(a,b,1);
}
int q;cin>>q;
auto Ask=[&](int a,int b,int c,int d){
if(a>b||c>d) return 0LL;
return bit.ask(b,d)-bit.ask(b,c-1)-bit.ask(a-1,d)+bit.ask(a-1,c-1);
};
F(i,q){
int a,b,c,d;cin>>a>>b>>c>>d;
cout<<Ask(a,b,c,d)+Ask(c,d,a,b)-Ask(max(a,c),min(b,d),max(a,c),min(b,d))<<"\n";
}
}
int32_t main(){
#ifdef LOCAL
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
#endif // LOCAL
IOS;
int t=1;
gen();
//cin>>t;
FF(i,1,t+1){
//cout<<"Case #"<<i<<": ";
sol();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
44016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
44016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
44016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
44016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
778 ms |
44016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
