Submission #474926

#	Time	Username	Problem	Language	Result	Execution time	Memory
474926		freddy645645	Group Photo (JOI21_ho_t3)	C++17	0 / 100	778 ms	44016 KiB

Main

#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();
    }
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 32
• Subtask 4: 0 / 20
• Subtask 5: 0 / 36