Submission #157199

#TimeUsernameProblemLanguageResultExecution timeMemory
157199manh9203Examination (JOI19_examination)C++17
100 / 100
2657 ms257876 KiB
#include<bits/stdc++.h> using namespace std; #define fi first #define se second #pragma GCC optimize("O3") const int N = 3e5 + 5; long long n,w,h,q,x[N],y[N],z[N],ans[N],cnt; pair<long long,long long> stu[N]; pair<pair<int,int>,long long> com[N]; map<long long,int> idx,idy; vector<long long> dmx,dmy,pos[N],node1[4*N]; vector<int> fen[4*N],point[N],query[N]; vector<pair<long long,int> > node[4*N]; //compress void build1(int id,int l,int r,int i,int vt){ if(l>i || r<i){ return; } if(l == r){ node[id].push_back({com[vt].se, vt}); node1[id].push_back(com[vt].se); return; } int mid = (l + r) >> 1; build1(id<<1, l, mid, i, vt); build1(id<<1|1, mid+1, r, i, vt); node[id].push_back({com[vt].se, vt}); node1[id].push_back(com[vt].se); } void build(int id,int l,int r){ if(l == r){ sort(node[id].begin(), node[id].end()); sort(node1[id].begin(), node1[id].end()); for(int i = 0; i < node[id].size(); i++){ pos[node[id][i].se].push_back(i + 1); } fen[id].assign(node[id].size() + 5, 0); return; } int mid = (l + r) >> 1; build(id<<1, l, mid); build(id<<1|1, mid+1, r); sort(node[id].begin(), node[id].end()); sort(node1[id].begin(), node1[id].end()); for(int i = 0; i < node[id].size(); i++){ pos[node[id][i].se].push_back(i + 1); } fen[id].assign(node[id].size() + 5, 0); } //upd BIT void upd(int id,int val,int index){ for(int i = id; i <= node[index].size(); i += (i&-i)){ fen[index][i] += val; } } int get_sum(int id,int index){ int sum = 0; for(int i = id; i >= 1; i -= (i&-i)){ sum += fen[index][i]; } return sum; } //sweep update void update(int id,int l,int r,int i,int vt){ if(l>i || r<i){ return; } if(l == r){ cnt++; upd(pos[vt][cnt], 1, id); return; } int mid = (l + r) >> 1; update(id<<1, l, mid, i, vt); update(id<<1|1, mid+1, r, i, vt); cnt++; upd(pos[vt][cnt], 1, id); } //ans query int get(int id,int l,int r,int i,int j,long long val){ if(l>j || r<i || i>j){ return 0; } if(l>=i && r<=j){ if(node1[id].size() == 0 || node1[id][node1[id].size()-1] < val){ return 0; }else{ int dm1 = lower_bound(node1[id].begin(), node1[id].end(), val) - node1[id].begin(); return get_sum(node1[id].size(), id) - get_sum(dm1, id); } } int mid = (l + r) >> 1; return get(id<<1, l, mid, i, j, val) + get(id<<1|1, mid+1, r, i, j, val); } //main int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for(int i=1;i<=n;i++){ cin >> stu[i].fi >> stu[i].se; if(idx[stu[i].fi] == 0){ idx[stu[i].fi] = 1; dmx.push_back(stu[i].fi); } if(idy[stu[i].se] == 0){ idy[stu[i].se] = 1; dmy.push_back(stu[i].se); } } for(int i=1;i<=q;i++){ cin >> x[i] >> y[i] >> z[i]; if(idx[x[i]] == 0){ idx[x[i]] = 1; dmx.push_back(x[i]); } if(idy[y[i]] == 0){ idy[y[i]] = 1; dmy.push_back(y[i]); } } sort(dmx.begin(), dmx.end()); sort(dmy.begin(), dmy.end()); w = dmx.size(); h = dmy.size(); for(int i=0;i<dmx.size();i++){ idx[dmx[i]] = i+1; } for(int i=0;i<dmy.size();i++){ idy[dmy[i]] = i+1; } for(int i=1;i<=n;i++){ com[i].fi.fi = idx[stu[i].fi]; com[i].fi.se = idy[stu[i].se]; com[i].se = stu[i].fi + stu[i].se; } for(int i=1;i<=q;i++){ x[i] = idx[x[i]]; y[i] = idy[y[i]]; query[x[i]].push_back(i); } sort(com+1, com+1+n); for(int i=1;i<=n;i++){ build1(1, 1, h, com[i].fi.se, i); point[com[i].fi.fi].push_back(i); } build(1, 1, h); for(int i = w; i >= 1; i--){ for(int j: point[i]){ cnt = -1; update(1, 1, h, com[j].fi.se, j); } for(int j: query[i]){ ans[j] = get(1, 1, h, y[j], h, z[j]); } } for(int i=1;i<=q;i++){ cout << ans[i] << "\n"; } }

Compilation message (stderr)

examination.cpp: In function 'void build(int, int, int)':
examination.cpp:35:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < node[id].size(); i++){
                  ~~^~~~~~~~~~~~~~~~~
examination.cpp:46:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < node[id].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = id; i <= node[index].size(); i += (i&-i)){
                  ~~^~~~~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:129:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmx.size();i++){
              ~^~~~~~~~~~~
examination.cpp:132:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<dmy.size();i++){
              ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...