Submission #62923

#TimeUsernameProblemLanguageResultExecution timeMemory
62923BenqSpiral (BOI16_spiral)C++11
31 / 100
5 ms660 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef complex<ld> cd; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; typedef vector<int> vi; typedef vector<ld> vd; typedef vector<ll> vl; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<cd> vcd; template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; #define FOR(i, a, b) for (int i=a; i<(b); i++) #define F0R(i, a) for (int i=0; i<(a); i++) #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--) #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--) #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() const int MOD = 1000000007; const ll INF = 1e18; const int MX = 100001; ll po (ll b, ll p) { return !p?1:po(b*b%MOD,p/2)*(p&1?b:1)%MOD; } ll inv (ll b) { return po(b,MOD-2); } int ad(int a, int b) { return (a+b)%MOD; } int sub(int a, int b) { return (a-b+MOD)%MOD; } int mul(int a, int b) { return (ll)a*b%MOD; } int AD(int& a, int b) { return a = ad(a,b); } int SUB(int& a, int b) { return a = sub(a,b); } int MUL(int& a, int b) { return a = mul(a,b); } int eval2(int x) { return mul(mul(mul(x,ad(x,1)),ad(mul(2,x),1)),inv(6)); } int getSum(int l, int r, int deg) { if (deg == 0) return ad(sub(r,l),1); if (deg == 1) return mul(mul(ad(l,r),ad(sub(r,l),1)),inv(2)); if (deg == 2) return sub(eval2(r),eval2(l-1)); exit(5); } vi operator+(const vi& l, const vi& r) { vi res(max(sz(l),sz(r))); F0R(i,sz(l)) res[i] = l[i]; F0R(i,sz(r)) AD(res[i],r[i]); return res; } vi operator-(const vi& l, const vi& r) { vi res(max(sz(l),sz(r))); F0R(i,sz(l)) res[i] = l[i]; F0R(i,sz(r)) SUB(res[i],r[i]); return res; } vi operator*(const vi& l, const vi& r) { vi x(sz(l)+sz(r)-1); F0R(i,sz(l)) F0R(j,sz(r)) AD(x[i+j],mul(l[i],r[j])); return x; } vi operator*(const vi& l, const int& r) { vi L = l; for (int& i: L) MUL(i,r); return L; } vi operator+=(vi& l, const vi& r) { return l = l+r; } vi operator-=(vi& l, const vi& r) { return l = l-r; } template<class T> vi operator*=(vi& l, const T& r) { return l = l*r; } std::ostream& operator<<(std::ostream &strm, const vi& a) { cout << "{"; F0R(i,sz(a)) { if (i) cout << ", "; cout << a[i]; } cout << "}\n"; return strm; } vi interpolate(vpi v) { vi ret; F0R(i,sz(v)) { vi prod = {1}; int todiv = 1; F0R(j,sz(v)) if (i != j) { MUL(todiv,sub(v[i].f,v[j].f)); vi tmp = {sub(0,v[j].f),1}; prod *= tmp; } ret += prod*mul(inv(todiv),v[i].s); } return ret; } int eval(vi v, int y) { vpi part; part.pb({0,0}); F0R(i,sz(v)) part.pb({i+1,ad(part.back().s,v[i])}); vi z = interpolate(part); int cur = 1, ret = 0; F0R(i,sz(z)) { AD(ret,mul(z[i],cur)); MUL(cur,y); } return ret; } int get(int a, int b) { if (a == 0 && b == 0) return 1; int r = max(abs(a),abs(b)); if (a == r && b > -r) return (2*r-1)*(2*r-1)+r+b; if (b == r) return (2*r-1)*(2*r-1)+3*r-a; if (a == -r) return (2*r-1)*(2*r-1)+5*r-b; return (2*r-1)*(2*r-1)+7*r+a; } int n,q; int brute(int x1, int x2, int y1, int y2) { int ans = 0; FOR(i,x1,x2+1) FOR(j,y1,y2+1) ans += get(i,j); return ans; } int get1(int x, int y) { // y > 0, y <= x // (2*a-1)*(2*a-1)+a+b; y = min(y,x); vi v; FOR(Y,1,min(y,4)+1) { int t = mul(4,getSum(Y,x,2)); t = sub(t,mul(3,getSum(Y,x,1))); t = ad(t,mul(ad(1,Y),getSum(Y,x,0))); v.pb(t); } return eval(v,y); } int get2(int x, int y) { // y>x, x >= 0 // (2*r-1)*(2*r-1)+3*r-a; x = min(x,y); vi v; F0R(X,min(x+1,4)) { int t = mul(4,getSum(X+1,y,2)); t = sub(t,getSum(X+1,y,1)); // cout << t << "\n"; t = ad(t,mul(getSum(X+1,y,0),sub(1,X))); /*cout << t << "\n"; cout << "AH " << X+1 << " " << y << " " << t << "\n";*/ v.pb(t); } return eval(v,x+1); } int solve(int x1, int x2, int y1, int y2) { assert(x1 == 1 && y1 == 1); // cout << get2(x2,y2) << "\n"; int ans = sub(ad(get1(x2,y2),get2(x2,y2)),get2(0,y2)); // cout << ans << " " << brute(x1,x2,y1,y2) << "\n"; // assert(ans == brute(x1,x2,y1,y2)); return ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; F0R(i,q) { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; cout << solve(x1,x2,y1,y2) << "\n"; } /*cout << get(1,0) << "\n"; FORd(j,-5,6) { FOR(i,-5,6) cout << get(i,j) << "\t"; cout << "\n"; }*/ } /* Look for: * the exact constraints (multiple sets are too slow for n=10^6 :( ) * special cases (n=1?) * overflow (ll vs int?) * array bounds */
#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...