QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#130143 | #3300. Cactus Competition | Alinxester | WA | 3ms | 11868kb | C++14 | 2.5kb | 2023-07-23 17:11:10 | 2023-07-23 17:11:12 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define ll long long
#define mod 998244353
#define int128 __int128
#define base 23333
#define base2 19260817
#define db double
#define ldb long double
#define eps 1e-8
#define cmpeps 1e-18
#define lowbit(x) (x & -x)
#define un unsigned
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define go_(i,u) for (int i = head[u]; ~i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
using namespace std;
//char buf[1<<21],*p1=buf,*p2=buf;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
t = 0; char f = 0, ch = getchar(); ldb d = 0.1;
while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
if (ch == '.') {
ch = getchar();
while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
}
t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read (T& t, Args&... args) { read(t); read(args...); }
inline void write (int x) {
if (x >= 10) write(x / 10);
cout << (ll) (x % 10);
}
const int N = 2e5 + 2, INF = 1e18 + 2;
int n, m, a[N], b[N], p[N];
int L[N], R[N], lvis[N], rvis[N];
int sum[N], ans;
inline bool p_cmp (int x, int y) {
return a[x] > a[y]; }
signed main() {
read(n, m);
rep (i, 1, n) read(a[i]), p[i] = i;
rep (i, 1, m) read(b[i]);
sort(p + 1, p + n + 1, p_cmp);
int l = 1, r = m, lmn, rmn;
lmn = rmn = INF;
rep (i, 1, n) {
for (; l <= m && a[p[i]] + b[l] < 0; ++l) lmn = min(lmn, b[l]);
for (; r && a[p[i]] + b[r] < 0; --r) rmn = min(rmn, b[r]);
L[i] = lmn, R[i] = rmn;
}
drep (i, n, 1) {
for (int j = p[i]; j && !lvis[j] && L[i] + a[j] < 0; --j) lvis[j] = 1;
for (int j = p[i]; j <= n && !rvis[j] && R[i] + a[j] < 0; --j) rvis[i] = 1;
}
int mx = -INF, mn = INF;
rep (i, 1, m) mn = min(mn, b[i]), mx = max(mx, b[i]);
rep (i, 1, n) sum[i] = sum[i - 1] + (!rvis[i]);
l = r = n + 1;
drep (i, n, 1) {
if (mn + a[i] >= 0) l = i;
if (mx + a[i] < 0) r = i;
if (!lvis[i] && l < r) ans += sum[r - 1] - sum[l - 1];
}
printf("%lld\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 11848kb
input:
3 3 -1 0 1 -1 0 1
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 0ms
memory: 11860kb
input:
3 3 -1 0 1 1 0 1
output:
5
result:
ok single line: '5'
Test #3:
score: 0
Accepted
time: 3ms
memory: 11852kb
input:
10 10 145195799 312862766 143966779 -11056226 -503624929 636383890 -182650312 -382759112 -290767690 377894950 -845235881 -418232930 -600566938 -957917357 -181139226 125255273 -175406945 740226783 -750456842 325848662
output:
0
result:
ok single line: '0'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 11868kb
input:
10 10 923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590 553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615
output:
20
result:
wrong answer 1st lines differ - expected: '13', found: '20'