Submission #1079855

#TimeUsernameProblemLanguageResultExecution timeMemory
1079855KhoaDuyExamination (JOI19_examination)C++14
0 / 100
397 ms27820 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define endl '\n' struct cube{ int a,b,c,idx; }; const int MAXN=1e5; int ans[MAXN]={0}; int bit[2*MAXN+1]={0}; void update(int i,int x){ for(;i<=2*MAXN;i+=(i&(-i))){ bit[i]+=x; } } int pre(int i){ int curr=0; for(;i;i-=(i&(-i))){ curr+=bit[i]; } return curr; } int query(int l,int r){ return pre(r)-pre(l-1); } bool cmp(cube &a,cube &b){ return (a.b>b.b); } bool cmp2(cube &a,cube &b){ return (a.a<b.a); } void dnc(vector<cube> &v){ if(v.size()<=1){ return; } int mid=(v.size()>>1); vector<cube> v1,v2; for(int i=0;i<mid;i++){ v1.push_back(v[i]); } for(int i=mid;i<v.size();i++){ v2.push_back(v[i]); } dnc(v1),dnc(v2); sort(v.begin(),v.end(),cmp); /*cout << "GOT" << endl; cout << "V1: " << endl; for(int i=0;i<v1.size();i++){ cout << v1[i].a << ' ' << v1[i].b << ' ' << v1[i].c << ' ' << v1[i].idx << endl; } cout << "V2: " << endl; for(int i=0;i<v2.size();i++){ cout << v2[i].a << ' ' << v2[i].b << ' ' << v2[i].c << ' ' << v2[i].idx << endl; }*/ int ptr=0; for(int i=0;i<v2.size();i++){ while(ptr<v1.size()&&v1[ptr].b>v2[i].b){ if(v1[ptr].idx!=-1){ ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN); } ptr++; } if(v2[i].idx==-1){ update(v2[i].c,1); } } while(ptr<v1.size()){ if(v1[ptr].idx!=-1){ ans[v1[ptr].idx]+=query(v1[ptr].c,2*MAXN); } ptr++; } for(int i=0;i<v2.size();i++){ if(v2[i].idx==-1){ update(v2[i].c,-1); } } } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,q; cin >> n >> q; vector<cube> v; map<int,int> mp; for(int i=0;i<n;i++){ int s,t; cin >> s >> t; v.push_back({s,t,s+t,-1}); mp[s+t]=1; } for(int i=0;i<q;i++){ int x,y,z; cin >> x >> y >> z; v.push_back({x,y,z,i}); mp[z]=1; } int idx=1; for(pair<const int,int> &x:mp){ x.second=idx; idx++; } for(int i=0;i<v.size();i++){ v[i].c=mp[v[i].c]; } for(int i=0;i<v.size();i++){ // cout << v[i].a << ' ' << v[i].b << ' ' << v[i].c << ' ' << v[i].idx << endl; } sort(v.begin(),v.end(),cmp2); dnc(v); for(int i=0;i<q;i++){ cout << ans[i] << endl; } }

Compilation message (stderr)

examination.cpp: In function 'void dnc(std::vector<cube>&)':
examination.cpp:41:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i=mid;i<v.size();i++){
      |                   ~^~~~~~~~~
examination.cpp:56:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp:57:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         while(ptr<v1.size()&&v1[ptr].b>v2[i].b){
      |               ~~~^~~~~~~~~~
examination.cpp:67:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     while(ptr<v1.size()){
      |           ~~~^~~~~~~~~~
examination.cpp:73:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i=0;i<v2.size();i++){
      |                 ~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:103:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~
examination.cpp:106:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<cube>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for(int i=0;i<v.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...