Submission #1022188

#TimeUsernameProblemLanguageResultExecution timeMemory
1022188dostsExamination (JOI19_examination)C++17
0 / 100
482 ms1048576 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define vi vector<int> #define all(xx) xx.begin(),xx.end() #define ps(xxx) cout << (xxx) << endl; const int N = 3e5+1,inf = 2e18; struct Query { int id,x,y,z; }; vi v; int idx(int x) { return upper_bound(all(v),x) - v.begin(); } struct BIT { int n,m; vector<vi> bit; BIT(int nn,int mm) { n = nn, m = mm; bit.assign(n+1,vi(m+1,0)); } void put(int x,int y,int v) { for (int i=x;i<=n;i+=i&-i) { for (int j=y;j<=n;j+=j&-j) { bit[i][j]+=v; } } } int get(int x,int y) { int ans = 0; for (int i=x;i>0;i-=i&-i) { for (int j=y;j>0;j-=j&-j) { ans+=bit[i][j]; } } return ans; } }; void solve() { int n,q; cin >> n >> q; vi a(n+1),b(n+1); for (int i=1;i<=n;i++) cin >> a[i] >> b[i]; vi inds(n+1); iota(inds.begin(),inds.end(),0); sort(inds.begin()+1,inds.end(),[&](int x,int y) { return a[x]+b[x] < a[y]+b[y]; }); vector<Query> queries(q); vi ans(q); for (int i=0;i<q;i++) { cin >> queries[i].x >> queries[i].y >> queries[i].z; queries[i].id = i; } for (int i=1;i<=n;i++) v.push_back(-a[i]),v.push_back(-b[i]); for (int i=1;i<=q;i++) v.push_back(-queries[i].x),v.push_back(-queries[i].y); sort(all(v)); v.erase(unique(all(v)),v.end()); sort(queries.begin(), queries.end(),[&](const Query& x,const Query& y) { return x.z > y.z; }); int sz = v.size(); BIT ft(sz,sz); int ptr = n+1; for (auto Q : queries) { int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id; while (ptr > 1 && a[inds[ptr-1]]+b[inds[ptr-1]] >= Z) { --ptr; ft.put(idx(-a[inds[ptr]]),idx(-b[inds[ptr]]),1); } ans[Q.id] = ft.get(idx(-X),idx(-Y)); } for (int i=0;i<q;i++) cout << ans[i] << '\n'; } signed main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #ifdef Dodi freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }

Compilation message (stderr)

examination.cpp: In function 'void solve()':
examination.cpp:81:39: warning: unused variable 'ID' [-Wunused-variable]
   81 |         int X = Q.x, Y = Q.y, Z = Q.z,ID = Q.id;
      |                                       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...