Submission #69393

#TimeUsernameProblemLanguageResultExecution timeMemory
69393BenqDragon 2 (JOI17_dragon2)C++14
60 / 100
974 ms263168 KiB
#pragma GCC optimize ("O3") #pragma GCC target ("sse4") #include <bits/stdc++.h> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/assoc_container.hpp> #include <ext/rope> using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; 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 = 30001; namespace geo { template<class T> istream& operator>> (istream& is, complex<T>& p) { T value; is >> value; p.real(value); is >> value; p.imag(value); return is; } void nor(pd& x) { if (x.f < -M_PIl) x.f += 2*M_PIl, x.s += 2*M_PIl; } ld area(cd a, cd b, cd c) { return (conj(b-a)*(c-a)).imag(); } } using namespace geo; struct BIT { vector<array<ld,3>> toUpd; vector<pair<array<ld,3>,int*>> toQuery; map<ld,int> m; vi bit; void upd(ld x, int y) { // cout << "OOPS " << x << " " << y << "\n"; for (int X = m[x]; X < sz(bit); X += (X&-X)) bit[X] += y; } void query(ld x, int y, int* z) { int t = 0; auto it = m.ub(x); // cout << z << "\n"; for (int X = (it == m.begin() ? 0 : prev(it)->s); X; X -= (X&-X)) { (*z) += y*bit[X]; t += y*bit[X]; } // cout << "HUH " << x << " " << y << " " << t << " " << z << "\n"; } void prop() { for (auto x: toUpd) m[x[1]] = 0; int co = 0; for (auto& a: m) a.s = ++co; bit.resize(sz(m)+1); sort(all(toUpd)), sort(all(toQuery)); int ind = 0; for (auto x: toQuery) { while (ind < sz(toUpd) && toUpd[ind][0] <= x.f[0]) { upd(toUpd[ind][1],toUpd[ind][2]); ind ++; } query(x.f[1],x.f[2],x.s); } } }; int N,M,group[MX],ans[100001]; vi member[MX]; cd pos[MX], h[2]; pd POS[MX]; pair<pd,pd> BOUND[MX]; vpi query[MX]; BIT z[MX]; void process1(int x) { BIT z; array<int,MX> co; co.fill(0); // cout << "OH " << x << "\n"; for (int a: member[x]) { // cout << "HA " << a << "\n"; z.toUpd.pb({BOUND[a].f.f,BOUND[a].s.f,1}); z.toUpd.pb({BOUND[a].f.s,BOUND[a].s.s,1}); z.toUpd.pb({BOUND[a].f.f,BOUND[a].s.s,-1}); z.toUpd.pb({BOUND[a].f.s,BOUND[a].s.f,-1}); } FOR(a,1,N+1) { z.toQuery.pb({{POS[a].f,POS[a].s,1},&co[group[a]]}); z.toQuery.pb({{POS[a].f+2*M_PIl,POS[a].s,1},&co[group[a]]}); z.toQuery.pb({{POS[a].f,POS[a].s+2*M_PIl,1},&co[group[a]]}); z.toQuery.pb({{POS[a].f+2*M_PIl,POS[a].s+2*M_PIl,1},&co[group[a]]}); } z.prop(); /*cout << "FINAL\n"; FOR(i,1,M+1) cout << co[i] << " "; cout << "\n";*/ for (auto a: query[x]) ans[a.s] = co[a.f]; // exit(0); } void process2(int x) { for (auto a: query[x]) for (int b: member[x]) { z[a.f].toQuery.pb({{BOUND[b].f.s,BOUND[b].s.s,1},&ans[a.s]}); z[a.f].toQuery.pb({{BOUND[b].f.f,BOUND[b].s.s,-1},&ans[a.s]}); z[a.f].toQuery.pb({{BOUND[b].f.s,BOUND[b].s.f,-1},&ans[a.s]}); z[a.f].toQuery.pb({{BOUND[b].f.f,BOUND[b].s.f,1},&ans[a.s]}); } } void process(int x) { //process1(x); if ((ll)sz(query[x])*sz(member[x]) >= N) process1(x); else process2(x); } void input() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> M; FOR(i,1,N+1) { cin >> pos[i] >> group[i]; member[group[i]].pb(i); } F0R(i,2) cin >> h[i]; FOR(i,1,N+1) { POS[i].f = arg(pos[i]-h[0]); POS[i].s = arg(pos[i]-h[1]); if (area(h[0],h[1],pos[i]) > 0) BOUND[i] = {{POS[i].f-M_PIl,POS[i].f},{POS[i].s,POS[i].s+M_PIl}}; else BOUND[i] = {{POS[i].f,POS[i].f+M_PIl},{POS[i].s-M_PIl,POS[i].s}}; nor(BOUND[i].f); nor(BOUND[i].s); // cout << i << " " << POS[i].f << " " << POS[i].s << " " << BOUND[i].f.f << " " << BOUND[i].f.s << " " << BOUND[i].s.f << " " << BOUND[i].s.s << "\n"; } } int main() { input(); int Q; cin >> Q; F0R(i,Q) { int f,g; cin >> f >> g; query[f].pb({g,i}); } FOR(i,1,M+1) process(i); FOR(i,1,M+1) { for (int a: member[i]) { z[i].toUpd.pb({POS[a].f,POS[a].s,1}); z[i].toUpd.pb({POS[a].f+2*M_PIl,POS[a].s,1}); z[i].toUpd.pb({POS[a].f,POS[a].s+2*M_PIl,1}); z[i].toUpd.pb({POS[a].f+2*M_PIl,POS[a].s+2*M_PIl,1}); } z[i].prop(); } F0R(i,Q) cout << ans[i] << "\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 * if you have no idea just guess the appropriate well-known algo instead of doing nothing :/ */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...