Submission #95344

#TimeUsernameProblemLanguageResultExecution timeMemory
95344Retro3014절취선 (JOI14_ho_t5)C++17
20 / 100
204 ms19456 KiB
#include <iostream> #include <vector> #include <stdio.h> #include <algorithm> #include <map> using namespace std; typedef long long ll; int W, H, N; struct LINE{ LINE (int x, int y1, int y2) : x(x), y1(y1), y2(y2) {} int x; int y1, y2; bool operator <(const LINE &a)const{ return x<a.x; }}; vector<LINE> line; struct POINT{ POINT (int x, int y, int z) : x(x), y(y), z(z) {} int x, y, z; bool operator <(const POINT &a)const{ if(x==a.x){ return z<a.z; } return x<a.x; }}; vector<POINT> p; struct SEG{ SEG (int l, int r, int sum) : l(l), r(r), sum(sum) {} int l, r; int sum; }; vector<SEG> seg1; ll ans = 1; //map<pair<int, int>, int> mp; int sum11(int idx, int s, int e, int x, int y){ if(idx==-1) return 0; if(x<=s && e<=y) return seg1[idx].sum; if(x>e || y<s) return 0; return sum11(seg1[idx].l, s, (s+e)/2, x, y) + sum11(seg1[idx].r, (s+e)/2+1, e, x, y); } void update11(int idx, int s, int e, int x, int y){ seg1[idx].sum+=y; if(s==e) return; if(x<=(s+e)/2){ if(seg1[idx].l==-1){ seg1[idx].l = seg1.size(); seg1.push_back({-1, -1, 0}); } update11(seg1[idx].l, s, (s+e)/2, x, y); }else{ if(seg1[idx].r==-1){ seg1[idx].r = seg1.size(); seg1.push_back({-1, -1, 0}); } update11(seg1[idx].r, (s+e)/2+1, e, x, y); } } int sum1(int x, int y) {return sum11(0, 0, H, x, y);} void update1(int x, int y) {update11(0, 0, H, x, y);} int main(){ scanf("%d%d%d", &W, &H, &N); seg1.push_back({-1, -1, 0}); for(int i=0; i<N; i++){ int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); if(a==c){ line.push_back({a, b, d}); }else{ p.push_back({a, b, 1}); p.push_back({c+1, b, -1}); } } //cout<<ans<<endl; p.push_back({0, 0, 1}); p.push_back({0, H, 1}); line.push_back({0, 0, H}); line.push_back({W, 0, H}); sort(p.begin(), p.end()); sort(line.begin(), line.end()); int idx = 0; ans-=(ll)(N+4); for(int i=0; i<line.size(); i++){ while(idx<p.size() && p[idx].x<=line[i].x){ POINT now = p[idx]; idx++; //cout<<'*'<<now.x<<' '<<now.y<<' '<<now.z<<endl; if(now.z==1){ update1(now.y, 1); }else{ update1(now.y, -1); } } int tmp = sum1(line[i].y1, line[i].y2); ans+=(ll)tmp; } printf("%lld", ans); }

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:85:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<line.size(); i++){
               ~^~~~~~~~~~~~
2014_ho_t5.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<p.size() && p[idx].x<=line[i].x){
         ~~~^~~~~~~~~
2014_ho_t5.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...