QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#33146 | #1780. Intact Intervals | YaoBIG# | WA | 9ms | 11580kb | C++17 | 3.5kb | 2022-05-28 22:21:21 | 2022-05-28 22:21:22 |
Judging History
answer
#include "bits/stdc++.h"
#define rep(i, a, n) for(auto i = a; i <= (n); i++)
#define per(i, a, n) for(auto i = n; i >= (a); i--)
#define pb push_back
#define mp make_pair
#define FI first
#define SE second
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a).size()
template<class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, T b) { if(b < a) { a = b; return 1; } return 0; }
using namespace std;
template<class A, class B> string to_string(pair<A, B> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string) s); }
string to_string(char c) { return "'" + string(1, c) + "'"; }
string to_string(bool x) { return x ? "true" : "false"; }
template<class A> string to_string(A v)
{
bool first = 1;
string res = "{";
for(const auto &x: v)
{
if (!first) res += ", ";
first = 0;
res += to_string(x);
}
res += "}";
return res;
}
template<class A, class B> string to_string(pair<A, B> p) { return "(" + to_string(p.FI) + ", " + to_string(p.SE) + ")"; }
void debug_out() { cerr << endl; }
template<class Head, class... Tail> void debug_out(Head H, Tail... T)
{
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) if(0) puts("No effect.")
#endif
using ll = long long;
// using LL = __int128;
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using db = double;
using ldb = long double;
const int maxn = 1'000'000;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
inline void chadd(int &x, int y) { x += y; if(x >= mod) x -= mod; }
inline void chsub(int &x, int y) { x -= y; if(x < 0) x += mod; }
using hashv = pair<int,int>;
const int mod1 = 1000000007;
const int mod2 = 1000050131;
inline int Madd(int x, int y, int mod) {return x+y<mod?x+y:x+y-mod;}
inline int Msub(int x, int y, int mod) {return x-y>=0?x-y:x-y+mod;}
hashv operator +(hashv a, hashv b) { return {Madd(a.FI, b.FI, mod1), Madd(a.SE, b.SE, mod2)}; }
hashv operator +(hashv a, int b) { return {Madd(a.FI, b, mod1), Madd(a.SE, b, mod2)}; }
hashv operator -(hashv a, hashv b) { return {Msub(a.FI, b.FI, mod1), Msub(a.SE, b.SE, mod2)}; }
hashv operator *(hashv a, hashv b) { return {1ll * a.FI * b.FI % mod1, 1ll * a.SE * b.SE % mod2}; }
hashv operator *(hashv a, int b) { return {1ll * a.FI * b % mod1, 1ll * a.SE * b % mod2}; }
const hashv base = {1000003, 1000033};
hashv pw[maxn+5];
int main()
{
ios::sync_with_stdio(0); cin.tie(0);
pw[0] = {1, 1};
rep(i, 1, maxn) pw[i] = pw[i - 1] * base;
int n; cin >> n;
vi a(n + 1), b(n + 1);
rep(i, 1, n) cin >> a[i];
rep(i, 1, n) cin >> b[i];
vi vec;
rep(i, 1, n) vec.pb(a[i]);
sort(all(vec));
vec.erase(unique(all(vec)), vec.end());
auto getid = [&](int x) { return lower_bound(all(vec), x) - vec.begin(); };
rep(i, 1, n) a[i] = getid(a[i]);
rep(i, 1, n) b[i] = getid(b[i]);
vector<hashv> hx(n + 1);
rep(i, 1, n) hx[i] = hx[i - 1] + pw[a[i]] - pw[b[i]];
map<hashv, int> dp;
dp[hx[0]] = 1;
int ans = 0;
rep(i, 1, n)
{
hashv h = hx[i];
int &val = dp[h];
chadd(ans, val);
chadd(val, (val + 1) % mod);
}
chsub(ans, 1);
printf("%d\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 9ms
memory: 11580kb
input:
2 10 9 9 10
output:
0
result:
ok single line: '0'
Test #2:
score: -100
Wrong Answer
time: 6ms
memory: 11424kb
input:
5 3 6 9 10 6 3 10 6 9 6
output:
10
result:
wrong answer 1st lines differ - expected: '4', found: '10'