Submission #673526

#TimeUsernameProblemLanguageResultExecution timeMemory
673526Carmel_Ab1Examination (JOI19_examination)C++17
100 / 100
1388 ms550756 KiB
/* #pragma GCC target ("avx2") #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") */ #include<bits/stdc++.h> //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //using namespace __gnu_pbds; using namespace std; typedef long double ld; typedef long long ll; typedef unsigned long long ull; typedef vector<int>vi; typedef vector<vector<int>>vvi; typedef vector<ll>vl; typedef vector<vl> vvl; typedef pair<int,int>pi; typedef pair<ll,ll> pl; typedef vector<pl> vpl; typedef vector<ld> vld; typedef pair<ld,ld> pld; typedef vector<pi> vpi; //typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;} #define all(x) x.begin(),x.end() #define YES out("YES") #define NO out("NO") #define out(x){cout << x << "\n"; return;} #define outfl(x){cout << x << endl;return;} #define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) #define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";} #define pb push_back #define umap unordered_map template<typename T> void read(vector<T>& v){ int n=v.size(); for(int i=0; i<n; i++) cin >> v[i]; } template<typename T> vector<T>UNQ(vector<T>a){ vector<T>ans; for(T t:a) if(ans.empty() || t!=ans.back()) ans.push_back(t); return ans; } void solve(); int main(){ GLHF; int t=1; //cin >> t; while(t--) solve(); } struct seg{ seg* lp=0,*rp=0; int l,r,m; int sum=0; seg(int l,int r):l(l),r(r),m((l+r)/2){} void expand(){ if(!lp)lp=new seg(l,m); if(!rp)rp=new seg(m,r); } void upd(int i,int v){ sum+=v; if(l+1==r) return; expand(); if(i<m) lp->upd(i,v); else rp->upd(i,v); } int qur(int a,int b){ if(b<=l || r<=a) return 0; if(a<=l && r<=b) return sum; expand(); return lp->qur(a,b) + rp->qur(a,b); } }; /* Basically what we do is split the queries into 2 types: type (1): queries where A+B>=C: then we only need to count S>=A, T>=B, (and then it applies that S+T>=A+B>=C). So we only need to count how many fulfil S>=A, T>=B. This can be done offline - sorting queries and pairs by S/A, then querying a segment tree on [B,inf]. type (2): queries where A+B<C: Now try to visualize pairs of (S[i],T[i]) on the cartesian plane. The restrictions of the queries can be modeled in the following way: \ | \ | \ |"This area is what we want" \| |\ ----------------------------------------------- "limit A" | \ | \"limit C" "limit B" Then we can count how many (S+T>=C AND T>=B) - (S+T>=C AND A<S). This can be done similarly to type (1) queries. Also see: https://codeforces.com/blog/entry/66022?#comment-501375 */ void solve() { int n,q; cin >> n >> q; vvl a(n,vl(2)); for(int i=0 ;i<n; i++) cin >> a[i][0] >> a[i][1]; vvl queries(q,vl(4)); for(int i=0; i<q; i++){ cin >>queries[i][0] >> queries[i][1] >> queries[i][2]; queries[i][3]=i; } sort(all(a)); sort(all(queries)); vi ans(q); seg ST(0,1e9 +10); for(int i=0; i<n; i++) ST.upd(a[i][1],1); for(int i=0,j=0; i<q; i++){ while(j<n && a[j][0]<queries[i][0]) ST.upd(a[j++][1],-1); if(queries[i][0]+queries[i][1]>=queries[i][2]) ans[queries[i][3]] = ST.qur(queries[i][1],1e9 + 2); } sort(all(a),[&](vl v1,vl v2){ return v1[0]+v1[1] < v2[0]+v2[1]; }); sort(all(queries),[&](vl v1,vl v2){ return v1[2]<v2[2]; }); ST = seg(0,1e9 + 10); for(int i=0; i<n;i++) ST.upd(a[i][1],1); for(int i=0,j=0; i<q; i++){ ll A=queries[i][0],B=queries[i][1],C=queries[i][2],ix=queries[i][3]; if(A+B>=C) continue; while(j<n && a[j][0]+a[j][1]<C) ST.upd(a[j][1],-1), j++; ans[ix] = ST.qur(B,1e9 + 2); } ST = seg(0,1e9 + 10); for(int i=0; i<n;i++) ST.upd(a[i][0],1); for(int i=0,j=0; i<q; i++){ ll A=queries[i][0],B=queries[i][1],C=queries[i][2],ix=queries[i][3]; if(A+B>=C) continue; while(j<n && a[j][0]+a[j][1]<C) ST.upd(a[j][0],-1), j++; ans[ix] -= ST.qur(0,A); } for(int x:ans) cout << x << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...