Submission #22735

#TimeUsernameProblemLanguageResultExecution timeMemory
22735크리콘 B번 문제는 그리디로 풀려요 (#40)Donut-shaped Enclosure (KRIII5_DE)C++98
2 / 7
1500 ms442404 KiB
#include<stdio.h> #include<algorithm> #include<stdlib.h> using namespace std; typedef long long lld; const lld MINF = -2000000000; struct intv { lld x, yl, yr; int sco; intv(lld x_=0, lld yl_=0, lld yr_=0, int sco_=0){ x=x_, yl=yl_, yr=yr_, sco=sco_; } bool operator< (const intv& c) const { if(x == c.x)return sco < c.sco; return x<c.x; } } ba[404000]; struct iix { int sum, mx; iix(int sum_=0, int mx_=0) : sum(sum_), mx(mx_) {} }; struct segtr { segtr *l, *r; lld s, e; iix key; segtr(lld s_=0, lld e_=0) : s(s_), e(e_) {l=NULL, r=NULL;} } *itr; int N, bcn, dap; lld L, R; void add(segtr* it, lld mi, lld mx, int v){ if(mi > mx)return; lld l = it->s, r = it->e; lld m = ((l-MINF)+(r-MINF))/2 + MINF; if(m == r && l < m)m--; // printf("%lld %lld %lld / %lld %lld\n", l, m, r, mi, mx); if(l == -1 && r == -1 && mi == 0)exit(0); if(l == mi && r == mx){ it->key.sum += v; it->key.mx += v; return; } if(it->l == NULL)it->l = new segtr(l, m); if(it->r == NULL)it->r = new segtr(m+1, r); if(mx <= m) add(it->l, mi, mx, v); else if(mi > m) add(it->r, mi, mx, v); else{ add(it->l, mi, m, v); add(it->r, m+1, mx, v); } it->key.mx = max(it->l->key.mx, it->r->key.mx) + it->key.sum; } int main(){ itr = new segtr; itr->s = -2000000000, itr->e = 2000000000; scanf("%d %lld %lld", &N, &L, &R); L--; for(int i=0; i<N; i++){ lld x, y; int s; scanf("%lld%lld%d", &x, &y, &s); ba[bcn++] = intv(x-R, y-R, y+R, s); ba[bcn++] = intv(x-L, y-L, y+L, -s); ba[bcn++] = intv(x+L+1, y-L, y+L, s); ba[bcn++] = intv(x+R+1, y-R, y+R, -s); } sort(ba, ba+bcn); for(int i=0; i<bcn; i++){ add(itr, ba[i].yl, ba[i].yr, ba[i].sco); int mx = itr->key.mx; if(dap < mx)dap = mx; } printf("%d", dap); return 0; }

Compilation message (stderr)

DE.cpp: In function 'int main()':
DE.cpp:59:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld %lld", &N, &L, &R); L--;
                                   ^
DE.cpp:62:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d", &x, &y, &s);
                                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...