Submission #1048174

#TimeUsernameProblemLanguageResultExecution timeMemory
1048174MinbaevExamination (JOI19_examination)C++17
0 / 100
126 ms11972 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #pragma GCC target("avx,avx2,fma") #pragma GCC optimize("Ofast,unroll-loops") using namespace std; using namespace __gnu_pbds; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define s second #define int long long #define ll long long #define pii pair<int,int> #define ar array template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int inf = 1e17 + 7; const int mod = 1e9 + 7; const int N = 3e5 + 5; const int md = 998244353; int binpow(int a, int b){ if(b == 0)return 1; if(b % 2 == 0){ int c = binpow(a,b/2); return (c*c)%mod; } return (binpow(a,b-1)*a)%mod; } int divi(int a, int b){ return (a*(binpow(b,mod-2)))%mod; } int n,m,k; int t[N*4]; void update(int tl, int tr, int v, int pos){ if(tl == tr){ t[v] = 1; //~ cout << tr << " " << v << "\n"; //~ cout << "\n"; return; } int tm = (tl+tr)/2; //~ cout << tl << " " << tr << " " << tm << " " << pos << "\n"; if(pos <= tm) update(tl,tm,v*2,pos); else update(tm+1,tr,v*2+1,pos); t[v] = t[v*2] + t[v*2+1]; } int get(int tl, int tr, int v, int l, int r){ if(r < tl || tr < l)return 0; if(l <= tl && tr <= r){ return t[v]; } int tm = (tl+tr)/2; return get(tl,tm,v*2,l,r) + get(tm+1,tr,v*2+1,l,r); } void solve(){ cin >> n >> m; vector<pii>v(n); for(auto &to:v)cin >> to.f >> to.s; sort(all(v)); vector<pii>a; for(int i = 0;i<n;i++){ a.pb({v[i].s, i}); } sort(all(a)); vector<pair<pii,int>>q(m); for(int i = 0;i<m;i++){ int p; cin >> q[i].f.s >> q[i].f.f >> p; q[i].s = i; } vector<int>ans1(m); sort(rall(q)); int cur = n - 1; for(int i = 0;i<m;i++){ while(cur >= 0 && a[cur].f >= q[i].f.f){ //~ cout << cur << " " << a[cur].s << "\n"; update(0,n-1,1,a[cur].s); cur -= 1; } //~ cout << "\n"; int l = 0, r = n-1, ans = -1; while(l<=r){ int mid = (l+r)/2; if(v[mid].f < q[i].f.s){ l = mid + 1; } else { ans = mid; r = mid - 1; } } ans1[q[i].s] = get(0, n-1, 1, ans, n-1); //~ cout << ans << " " << n-1 << "\n"; } for(auto to:ans1)cout << to << "\n"; } /* 5 4 35 100 70 70 45 15 80 40 20 95 20 50 0 10 10 0 60 60 0 0 100 0 */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); //~ ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...