結果
問題 | No.2501 Maximum Inversion Number |
ユーザー |
|
提出日時 | 2023-10-13 21:32:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 129 ms / 2,000 ms |
コード長 | 2,746 bytes |
コンパイル時間 | 1,060 ms |
コンパイル使用メモリ | 122,488 KB |
最終ジャッジ日時 | 2025-02-17 07:08:33 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
コンパイルメッセージ
main.cpp: In function ‘void solve()’: main.cpp:94:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 94 | scanf("%d%lld", &n, &m); | ~~~~~^~~~~~~~~~~~~~~~~~ main.cpp:96:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 96 | scanf("%lld", &l[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp:98:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 98 | scanf("%lld", &r[i]); | ~~~~~^~~~~~~~~~~~~~~ main.cpp: In function ‘int main()’: main.cpp:131:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 131 | scanf("%d", &t); | ~~~~~^~~~~~~~~~
ソースコード
//#pragma GCC optimize("Ofast") //#pragma GCC target("avx,avx2,fma") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native") #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <bitset> #include <array> #include <climits> using namespace std; #ifdef LOCAL #define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);} #else #define eprintf(...) 42 #endif using ll = long long; using ld = long double; using uint = unsigned int; using ull = unsigned long long; using pii = pair<int, int>; using pli = pair<ll, int>; using pll = pair<ll, ll>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); ll myRand(ll B) { return (ull)rng() % B; } #define mp make_pair #define all(x) (x).begin(),(x).end() clock_t startTime; double getCurrentTime() { return (double)(clock() - startTime) / CLOCKS_PER_SEC; } ll floor_div(ll x, ll y) { assert(y != 0); if (y < 0) { y = -y; x = -x; } if (x >= 0) return x / y; return (x + 1) / y - 1; } ll ceil_div(ll x, ll y) { assert(y != 0); if (y < 0) { y = -y; x = -x; } if (x <= 0) return x / y; return (x - 1) / y + 1; } const int N = 200200; ll l[N], r[N]; ll a[N]; int n; ll m; ll setTo(ll x) { ll sum = 0; for (int i = 0; i < n; i++) { if (r[i] < x) { a[i] = r[i]; } else if (l[i] > x) { a[i] = l[i]; } else { a[i] = x; } sum += a[i]; } return sum; } void solve() { scanf("%d%lld", &n, &m); for (int i = 0; i < n; i++) scanf("%lld", &l[i]); for (int i = 0; i < n; i++) scanf("%lld", &r[i]); ll L = -1, R = m + 1; while(R - L > 1) { ll x = (L + R) / 2; if (setTo(x) < m) L = x; else R = x; } ll sum = setTo(R) - m; for (int i = 0; i < n; i++) { if (sum > 0 && a[i] == R && l[i] < R) { a[i]--; sum--; } } if (sum != 0) { printf("-1\n"); return; } ll ans = m * m; for (int i = 0; i < n; i++) ans -= a[i] * a[i]; ans /= 2; printf("%lld\n", ans); } int main() { startTime = clock(); // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); int t; scanf("%d", &t); for (int i = 1; i <= t; i++) { eprintf("--- Case #%d start ---\n", i); //printf("Case #%d: ", i); solve(); //printf("%lld\n", (ll)solve()); /* if (solve()) { printf("Yes\n"); } else { printf("No\n"); } */ eprintf("--- Case #%d end ---\n", i); eprintf("time = %.5lf\n", getCurrentTime()); eprintf("++++++++++++++++++++\n"); } return 0; }