Submission #291990

#TimeUsernameProblemLanguageResultExecution timeMemory
291990kajebiiiStrange Device (APIO19_strange_device)C++17
10 / 100
1077 ms84620 KiB
// Comment // #include <bits/stdc++.h> using namespace std; #define SZ(v) ((int)(v).size()) #define ALL(v) (v).begin(),(v).end() #define one first #define two second using ll = long long; using pi = pair<int, int>; const int INF = 0x3f3f3f3f; const ll LINF = 1ll * INF * INF; using pli = pair<ll, ll>; using ti = tuple<ll, ll, int>; ll gcd(ll a, ll b) { if(b == 0) return 1; return gcd(b, a%b); } int N; ll A, B, G; vector<ti> Lines; struct PT { ll x, y; // 0 <= x <= A/G, 0 <= y < B PT(ll _x, ll _y): x(_x), y(_y) {} PT up() { ll _x = x, _y = y; _y++; if(y == B) { _x++; _y = 0; } return PT(_x, _y); } }; vector<ll> getNums(ll t) { // t = (xA + n (A/G) + m) B + z; ll a = t / B, z = t % B; ll x = a / A, y = a % A; ll n = y / (A/G), m = y % (A/G); ll nums[4] = {x, n, m, z}; return vector<ll>(nums, nums+4); } int main() { cin >> N >> A >> B; G = gcd(A, B+1); for(int i=1; i<=N; i++) { ll x, y; scanf("%lld%lld", &x, &y); vector<ll> xs = getNums(x); vector<ll> ys = getNums(y); ll xabg = xs[0]*G + xs[1]; ll yabg = ys[0]*G + ys[1]; if(xabg+2 <= yabg) { printf("%lld\n", (A/G) * B); return 0; } Lines.emplace_back(xs[2], xs[3], +1); PT pt = PT(ys[2], ys[3]).up(); Lines.emplace_back(pt.x, pt.y, -1); if(xabg != yabg) { Lines.emplace_back(0, 0, +1); Lines.emplace_back(A/G, 0, -1); } } Lines.emplace_back(A/G, 0, 0); sort(ALL(Lines)); ll ans = 0; int now = 0; for(int i=0; i+1<SZ(Lines); i++) { ll x, y; int v; tie(x, y, v) = Lines[i]; ll nx, ny; int nv; tie(nx, ny, nv) = Lines[i+1]; now += v; if(now >= 1) { ans += (nx - x) * B + (ny - y); } } printf("%lld\n", ans); return 0; }

Compilation message (stderr)

strange_device.cpp: In function 'int main()':
strange_device.cpp:58:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |   ll x, y; scanf("%lld%lld", &x, &y);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...