QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33146#1780. Intact IntervalsYaoBIG#WA 9ms11580kbC++173.5kb2022-05-28 22:21:212022-05-28 22:21:22

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-28 22:21:22]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:11580kb
  • [2022-05-28 22:21:21]
  • 提交

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'