제출 #959275

#제출 시각아이디문제언어결과실행 시간메모리
959275qinBulldozer (JOI17_bulldozer)C++17
0 / 100
2047 ms348 KiB
//~ #pragma GCC optimize("O3") #include <bits/stdc++.h> #define fi first #define se second #define pn printf("\n") #define ssize(x) int(x.size()) #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define bitcount(x) __builtin_popcount(x) #define clz(x) __builtin_clz(x) #define ctz(x) __builtin_ctz(x) using namespace std; typedef __int128 ll; typedef pair<int, int> pii; typedef pair<int, ll> pil; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef long double db; #define int ll #define vv vector /*void read(int &a){ char c = getchar_unlocked(); a = 0; while(c<'0' || '9'<c) c = getchar_unlocked(); while('0'<=c&&c<='9') a = (a<<3)+(a<<1)+c-'0', c = getchar_unlocked(); }*/ int inf = 2e09; ll infll = 2e18; int mod = (1<<23)*119+1; struct pt{ int x, y, val; pt(){ x = 0, y = 0, val = 0; } pt(int X, int Y, int V){ x = X, y = Y, val = V; } bool operator <(const pt &a) const{ return x != a.x ? x < a.x : y < a.y; } }; const ll INF = 1e18; ll gcd_(ll a, ll b){ if(a > b) swap(a, b); while(a) b %= a, swap(a, b); return b; } struct fr{ ll a, b; fr(){ a = 0, b = 1; } fr(ll A, ll B){ if(B < 0) A = -A, B = -B; a = A/gcd_(A, B), b = B/gcd_(A, B); } bool operator <(const fr &x) const{ if(a == INF || x.a == INF) return a < x.a; return a*x.b < x.a*b; } bool operator ==(const fr &x) const{ if(a == INF || x.a == INF) return a == x.a; return a*x.b == x.a*b; } bool operator !=(const fr &x) const{ if(a == INF || x.a == INF) return a != x.a; return a*x.b != x.a*b; } }; db eps = 1e-15; bool equal(db a, db b){ return abs(b-a) < eps; } struct line{ fr a, b; int x1, x2, i, j; line(){ a = fr(), b = fr(), x1 = 0, x2 = 0, i = 0, j = 0; } line(int X1, int Y1, int X2, int Y2, int I, int J){ if(X1 == X2) a = fr(INF, 1), b = fr(), x1 = min(Y1, Y2), x2 = max(Y1, Y2); else a = fr(Y2-Y1, X2-X1), b = fr((Y1*(X2-X1)-(Y2-Y1))*X1,X2-X1), x1 = min(X1, X2), x2 = max(X1, X2); i = I, j = J; } bool operator <(const line &t) const{ if(a != t.a) return a < t.a; else if(b != t.b) return b < t.b; else if(x1 != t.x1) return x1 < t.x1; return x2 < t.x2; } }; int base = 1; struct seg{ struct Node{ int mx, mn, mx_delta; Node(){ mx = -infll, mn = infll, mx_delta = -infll; } Node(int val){ mx = val, mn = val, mx_delta = 0; } }; vv<Node> t; void init(int n, vv<int> &pf){ while(base < n) base <<= 1; t.resize(base<<1); for(int i = 1; i <= n; ++i) t[i+base-1] = Node(pf[i]); for(int i = base-1; i; --i){ t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx); t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn); t[i].mx_delta = max(t[i<<1|1].mx-t[i<<1].mn, max(t[i<<1].mx_delta, t[i<<1|1].mx_delta)); } } void update(int i, ll val){ //tutaj ewentualnie mozna dozylowywac for(i += base-1, t[i] = Node(val), i >>= 1; i; i >>= 1){ t[i].mx = max(t[i<<1].mx, t[i<<1|1].mx); t[i].mn = min(t[i<<1].mn, t[i<<1|1].mn); t[i].mx_delta = max(t[i<<1|1].mx-t[i<<1].mn, max(t[i<<1].mx_delta, t[i<<1|1].mx_delta)); } } int query(){ return max(t[1].mx, t[1].mx_delta); } }; void answer(){ int n; scanf("%lld", &n); vv<pt> p(n+1); for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val); sort(1+all(p)); vv<line> t((n*(n-1))/2); for(int i = 1, l = 0; i <= n-1; ++i) for(int j = i+1; j <= n; ++j, ++l) t[l] = line(p[i].x, p[i].y, p[j].x, p[j].y, i, j); sort(all(t)); //~ for(line &u : t) cout << setprecision(20) << fixed << u.a << " " << u.b <<"\n";//printf("%f %f %d %d\n", u.a, u.b, u.x1, u.x2); vv<ll> pf(n+1); vv<int> pos(n+1); for(int i = 1; i <= n; ++i) pf[i] = pf[i-1]+p[i].val, pos[i] = i; seg seg; seg.init(n, pf); int result = max(int(0ll), seg.query()); //~ printf("%lld\n", result); //~ for(int i = 1; i <= n; ++i) printf("%lld ", pf[i]); //~ pn; for(int i = 0; i < ssize(t); ++i){ int a = t[i].i, b = t[i].j; //assert(abs(pos[a]-pos[b]) == 1); if(pos[b] < pos[a]) swap(a, b); pf[pos[a]] += p[b].val-p[a].val; swap(pos[a], pos[b]); seg.update(pos[a], pf[pos[a]]), seg.update(pos[b], pf[pos[b]]); while(i+1 < ssize(t) && t[i+1].a == t[i].a){ ++i; a = t[i].i, b = t[i].j; //assert(abs(pos[a]-pos[b]) == 1); if(pos[b] < pos[a]) swap(a, b); pf[pos[a]] += p[b].val-p[a].val; swap(pos[a], pos[b]); seg.update(pos[a], pf[pos[a]]), seg.update(pos[b], pf[pos[b]]); } result = max(result, seg.query()); //~ printf("%lld\n", seg.query()); //~ for(int j = 1; j <= n; ++j) printf("%lld ", pf[j]); //~ pn; } printf("%lld\n", result); } signed main(){ int T = 1; //~ scanf("%d", &T); //~ ios_base::sync_with_stdio(0); cin.tie(0); //cin >> T; for(++T; --T; ) answer(); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

bulldozer.cpp: In function 'void answer()':
bulldozer.cpp:105:20: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
  105 |   int n; scanf("%lld", &n);
      |                 ~~~^   ~~
      |                    |   |
      |                    |   ll* {aka __int128*}
      |                    long long int*
bulldozer.cpp:107:41: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'll*' {aka '__int128*'} [-Wformat=]
  107 |   for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
      |                                      ~~~^           ~~~~~~~
      |                                         |           |
      |                                         |           ll* {aka __int128*}
      |                                         long long int*
bulldozer.cpp:107:45: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'll*' {aka '__int128*'} [-Wformat=]
  107 |   for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
      |                                          ~~~^                ~~~~~~~
      |                                             |                |
      |                                             long long int*   ll* {aka __int128*}
bulldozer.cpp:107:49: warning: format '%lld' expects argument of type 'long long int*', but argument 4 has type 'll*' {aka '__int128*'} [-Wformat=]
  107 |   for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
      |                                              ~~~^                     ~~~~~~~~~
      |                                                 |                     |
      |                                                 long long int*        ll* {aka __int128*}
bulldozer.cpp:145:14: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'll' {aka '__int128'} [-Wformat=]
  145 |   printf("%lld\n", result);
      |           ~~~^     ~~~~~~
      |              |     |
      |              |     ll {aka __int128}
      |              long long int
bulldozer.cpp:105:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   int n; scanf("%lld", &n);
      |          ~~~~~^~~~~~~~~~~~
bulldozer.cpp:107:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |   for(int i = 1; i <= n; ++i) scanf("%lld%lld%lld", &p[i].x, &p[i].y, &p[i].val);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#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...