Submission #1073065

#TimeUsernameProblemLanguageResultExecution timeMemory
1073065Mizo_CompilerAliens (IOI16_aliens)C++17
Compilation error
0 ms0 KiB
#include <bits/stdc++.h> #include "aliens.h" //#include "grader.cpp" using namespace std; typedef long long ll; #define F first #define S second #define sz(x) int(x.size()) #define all(x) x.begin(),x.end() #define pb push_back const int N = 1e5+5, M = 1e6+1; ll dp[N][2]; vector<int> R[M]; struct Line { mutable ll k, m, p; bool operator<(const Line &o) const { return k < o.k; } bool operator<(ll x) const { return p < x; } }; struct LineContainer : multiset<Line, less<>> { // (for doubles, use inf = 1/.0, div(a, b) = a / b) // (for minimum, insert -k and -m and return -ans) static const ll inf = LLONG_MAX; ll div(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } bool isect(iterator x, iterator y) { if(y == end()) return x -> p = inf, 0; if(x -> k == y -> k) x -> p = x -> m > y -> m ? inf : -inf; else x -> p = div(y -> m - x -> m, x -> k - y -> k); return x -> p >= y -> p; } void add(ll k, ll m) { k = -k; m = -m; auto z = insert({k, m, 0}), y = z++, x = y; while(isect(y, z)) z = erase(z); if(x != begin() && isect(--x, y)) isect(x, y = erase(y)); while((y = x) != begin() && (--x) -> p >= y -> p) isect(x, erase(y)); } int query(int x) { assert(!empty()); auto l = *lower_bound(x); return -(l.k * x + l.m); } }; ll l[N], r[N]; long long take_photos(int n, int m, int k, std::vector<int> roo, std::vector<int> co) { vector<ll> ro = roo; vector<ll> c = co; vector<pair<int, int>> rng; for (int i = 0; i < n; i++) { int l = min(ro[i], c[i]), rr = max(ro[i], c[i]); R[rr].push_back(l); } int mnl = 1e9; for (int i = m; i >= 0; i--) { sort(all(R[i])); for (auto &l : R[i]) { if (mnl > l)rng.push_back({l, i}); mnl = min(mnl, l); } R[i].clear(); } sort(all(rng)); n = sz(rng); k = min(k, sz(rng)); int cur = 0, prv = 1; for (int i = 0; i < n; i++) { l[i] = rng[i].F, r[i] = rng[i].S; dp[i][cur] = (r[i] - l[0] + 1ll) * (r[i] - l[0] + 1ll); //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n"; } for (int ii = 0; ii+1 < k; ii++) { cur ^= 1; prv ^= 1; LineContainer LC; for (int i = 0; i <= ii; i++) { ll cc = 0; if (i) { ll xx = max(0ll, r[i-1]-l[i]+1); cc = dp[i-1][prv] - (xx * xx); } LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc); dp[i][cur] = dp[i][prv]; //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n"; } for (int i = ii+1; i < n; i++) { ll cc = 0; if (i) { ll xx = max(0ll, r[i-1]-l[i]+1); cc = dp[i-1][prv] - (xx * xx); } LC.add(-2ll * l[i], -2ll * l[i] + (l[i] * l[i]) + cc); dp[i][cur] = (r[i] * r[i]) + (2ll * r[i]) + 1ll + LC.query(r[i]); //cout << l[i] << " " << r[i] << " " << dp[i][cur] << " ez\n"; } } return dp[n-1][cur]; }

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:52:21: error: conversion from 'vector<int>' to non-scalar type 'vector<long long int>' requested
   52 |     vector<ll> ro = roo;
      |                     ^~~
aliens.cpp:53:20: error: conversion from 'vector<int>' to non-scalar type 'vector<long long int>' requested
   53 |     vector<ll> c = co;
      |                    ^~