Submission #148778

#TimeUsernameProblemLanguageResultExecution timeMemory
148778mit한의대지망생 (#200)Crosses on the Grid (FXCUP4_cross)C++17
100 / 100
189 ms9960 KiB
#include <stdio.h> #include <algorithm> #include <vector> #include <map> using namespace std; typedef long long lli; class p { public: lli a, b; }; bool cmp(const p &i, const p &j) { if(i.a!=j.a) return i.a>j.a; else return i.b>j.b; } vector<lli> vx; int n, k, sz=1; p a[200000]; int bt[1<<19]; void upd(int k, int w) { while(k) { bt[k]+=w; k>>=1; } } int kth(int k) { if(bt[1]<k) return -1; int cur=1; while(cur<sz) { if(bt[cur*2+1]>=k) cur=(cur*2+1); else { k-=bt[cur*2+1]; cur=cur*2; } } return cur-sz; } long long SelectCross(int K, std::vector<int> I, std::vector<int> O) { n=I.size(); k=K; for(int i=0;i<n;i++) { a[i].a=I[i]; a[i].b=O[i]; vx.push_back(a[i].b); } if(k==1) { lli res=0; for(int i=0;i<n;i++) { lli w=a[i].b*a[i].b-(a[i].b-a[i].a)*(a[i].b-a[i].a); if(w>res) res=w; } return res; } sort(vx.begin(),vx.end()); vx.erase(unique(vx.begin(),vx.end()),vx.end()); while(sz<vx.size()) sz*=2; sort(a,a+n,cmp); lli res=0; for(int i=0;i<n;i++) { int id=lower_bound(vx.begin(),vx.end(),a[i].b)-vx.begin(); lli y=kth(k-1); if(y<0) { upd(sz+id,1); continue; } lli x=a[i].a; y=min(vx[y],a[i].b); lli w=y*y-(y-x)*(y-x); if(w>res) res=w; upd(sz+id,1); } return res; }

Compilation message (stderr)

cross.cpp: In function 'long long int SelectCross(int, std::vector<int>, std::vector<int>)':
cross.cpp:63:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(sz<vx.size()) sz*=2;
        ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...