Submission #369687

#TimeUsernameProblemLanguageResultExecution timeMemory
369687azberjibiouExamination (JOI19_examination)C++17
100 / 100
506 ms16272 KiB
#include <bits/stdc++.h> #define gibon ios::sync_with_stdio(false); cin.tie(0); using namespace std; #define fir first #define sec second #define ll long long #define pii pair<int, int> const int mxN=103000; typedef struct pro{ ll a, b, c; }pro; typedef struct qry{ int x, sy, ey, idx, typ; }qry; int N, Q; pro T[mxN]; pii A[mxN]; vector <int> coorx, coory, coorxy; vector <int> xy; int ans[mxN]; vector <qry> v; vector <pii> swp; int X, Y; int seg[4*mxN]; bool cmp1(qry p, qry q) { return p.x<q.x; } bool cmp2(pii a, pii b) { return a.fir<b.fir; } void init(int idx, int s, int e) { seg[idx]=0; if(s==e) return; int mid=(s+e)/2; init(2*idx, s, mid); init(2*idx+1, mid+1, e); } int solv(int idx, int s1, int e1, int s2, int e2) { if(s2>e1 || s1>e2) return 0; if(s2<=s1 && e1<=e2) return seg[idx]; int mid=(s1+e1)/2; return solv(2*idx, s1, mid, s2, e2)+solv(2*idx+1, mid+1, e1, s2, e2); } void upd(int idx, int s, int e, int pos) { if(pos<s || pos>e) return; seg[idx]++; if(s==e) return; int mid=(s+e)/2; upd(2*idx, s, mid, pos); upd(2*idx+1, mid+1, e, pos); } void make_coor() { for(int i=0;i<N;i++) coorx.push_back(A[i].fir), coory.push_back(A[i].sec); for(int i=0;i<N;i++) coorxy.push_back(A[i].fir+A[i].sec); coorx.push_back(1000000007); coory.push_back(1000000007); coorx.push_back(-2); coory.push_back(-2); coorxy.push_back(2000000007); coorxy.push_back(-2); sort(coorx.begin(), coorx.end()); sort(coory.begin(), coory.end()); sort(coorxy.begin(), coorxy.end()); coorx.erase(unique(coorx.begin(), coorx.end()), coorx.end()); coory.erase(unique(coory.begin(), coory.end()), coory.end()); coorxy.erase(unique(coorxy.begin(), coorxy.end()), coorxy.end()); X=coorx.size(), Y=coory.size(); } int main() { gibon cin >> N >> Q; for(int i=0;i<N;i++) cin >> A[i].fir >> A[i].sec; for(int i=0;i<Q;i++) cin >> T[i].a >> T[i].b >> T[i].c; make_coor(); for(int i=0;i<Q;i++) { int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin(); int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin(); //printf("i=%d, nx=%d, ny=%d\n", i, nx, ny); v.push_back({X-1, ny, Y-1, i, 1}); v.push_back({nx-1, ny, Y-1, i, -1}); if(T[i].a+T[i].b>=T[i].c) continue; v.push_back({nx-1, 0, ny-1, i, -1}); } sort(v.begin(), v.end(), cmp1); init(1, 0, Y-1); for(int i=0;i<N;i++) { int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin(); int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin(); swp.push_back({nx, ny}); } sort(swp.begin(), swp.end(), cmp2); //for(qry ele : v) printf("ele=%d, %d, %d, %d, %d\n", ele.x, ele.sy, ele.ey, ele.idx, ele.typ); int cur=0; for(int i=0;i<N;i++) { while(cur!=v.size() && v[cur].x<swp[i].fir) { ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } upd(1, 0, Y-1, swp[i].sec); } while(cur!=v.size()) { ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } //for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]); ///------------------------- v.clear(); for(int i=0;i<Q;i++) { if(T[i].a+T[i].b>=T[i].c) continue; int ny=lower_bound(coory.begin(), coory.end(), T[i].b)-coory.begin(); int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1; v.push_back({nxy, ny, Y-1, i, -1}); } sort(v.begin(), v.end(), cmp1); swp.clear(); for(int i=0;i<N;i++) { int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin(); int ny=lower_bound(coory.begin(), coory.end(), A[i].sec)-coory.begin(); swp.push_back({nxy, ny}); } sort(swp.begin(), swp.end(), cmp2); init(1, 0, Y-1); cur=0; for(int i=0;i<N;i++) { while(cur!=v.size() && v[cur].x<swp[i].fir) { ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } upd(1, 0, Y-1, swp[i].sec); } while(cur!=v.size()) { ans[v[cur].idx]+=solv(1, 0, Y-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } //for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]); ///-------------------------- v.clear(); for(int i=0;i<Q;i++) { if(T[i].a+T[i].b>=T[i].c) continue; int nxy=lower_bound(coorxy.begin(), coorxy.end(), T[i].c)-coorxy.begin()-1; int nx=lower_bound(coorx.begin(), coorx.end(), T[i].a)-coorx.begin(); v.push_back({nxy, nx, X-1, i, -1}); } sort(v.begin(), v.end(), cmp1); swp.clear(); for(int i=0;i<N;i++) { int nxy=lower_bound(coorxy.begin(), coorxy.end(), A[i].fir+A[i].sec)-coorxy.begin(); int nx=lower_bound(coorx.begin(), coorx.end(), A[i].fir)-coorx.begin(); swp.push_back({nxy, nx}); } sort(swp.begin(), swp.end(), cmp2); init(1, 0, X-1); cur=0; for(int i=0;i<N;i++) { while(cur!=v.size() && v[cur].x<swp[i].fir) { ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } upd(1, 0, X-1, swp[i].sec); } while(cur!=v.size()) { ans[v[cur].idx]+=solv(1, 0, X-1, v[cur].sy, v[cur].ey)*v[cur].typ; cur++; } //for(int i=0;i<Q;i++) printf("ans[%d]=%d\n", i, ans[i]); ///------------------- for(int i=0;i<N;i++) xy.push_back(A[i].fir+A[i].sec); sort(xy.begin(), xy.end()); for(int i=0;i<Q;i++) { if(T[i].a+T[i].b>=T[i].c) continue; ans[i]+=lower_bound(xy.begin(), xy.end(), T[i].c)-xy.begin(); } for(int i=0;i<Q;i++) cout << ans[i] << '\n'; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:111:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~
examination.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:146:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~
examination.cpp:174:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |         while(cur!=v.size() && v[cur].x<swp[i].fir)
      |               ~~~^~~~~~~~~~
examination.cpp:181:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<qry>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  181 |     while(cur!=v.size())
      |           ~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...