oj.uz

답안 #561322

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
561322 2022-05-12T16:06:39 Z wiwiho Misspelling (JOI22_misspelling) C++14
100 / 100
 3824 ms 274000 KB 
#include <bits/stdc++.h>

#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define eb emplace_back
#define pob pop_back()
#define mp make_pair
#define F first
#define S second
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;

using pii = pair<int, int>;
using pll = pair<ll, ll>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

const ll MOD = 1000000007;

void topos(ll& a){
    a = (a % MOD + MOD) % MOD;
}

int lowbit(int x){
    return x & -x;
}
struct BIT{
    vector<ll> bit;
    explicit BIT(int sz): bit(sz + 1) {}
    void modify(int x, int v){
        for(; x < bit.size(); x += lowbit(x)){
            bit[x] += v;
            bit[x] %= MOD;
        }
    }
    ll query(int x){
        ll ans = 0;
        for(; x > 0; x -= lowbit(x)){
            ans += bit[x];
            ans %= MOD;
        }
        return ans;
    }
    ll query(int l, int r){
        ll ans = query(r) - query(l - 1);
        topos(ans);
        return ans;
    }
};

struct event{
    int ty, op, v;
    // ty: 0:leq 1:geq
    // op: 0:add 1:remove
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<BIT> bit(26, BIT(n));
    vector<vector<ll>> dp(n + 1, vector<ll>(26));
    
    for(int i = 0; i < 26; i++){
        dp[1][i] = 1;
        bit[i].modify(1, 1);
    }

    multiset<int> leq, geq;
    vector<vector<event>> ev(n + 2);
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        if(a < b){ //leq
            ev[a + 1].eb(event({0, 0, a + 1}));
            ev[b + 1].eb(event({0, 1, a + 1}));
        }
        else{ // geq
            ev[b + 1].eb(event({1, 0, b + 1}));
            ev[a + 1].eb(event({1, 1, b + 1}));
        }
    }

    ll ans = 26;
    for(int i = 2; i <= n; i++){
        for(auto e : ev[i]){
            //cerr << "ev " << e.ty << " " << e.op << " " << e.v << "\n";
            if(e.ty == 0){
                if(e.op == 0) leq.insert(e.v);
                else leq.erase(leq.find(e.v));
            }
            else{
                if(e.op == 0) geq.insert(e.v);
                else geq.erase(geq.find(e.v));
            }
        }
        //cerr << "test " << i << "\n";
        //cerr << "leq ";
        //printv(leq, cerr);
        //cerr << "geq ";
        //printv(geq, cerr);
        
        int lstleq = leq.empty() ? 1 : *leq.rbegin();
        int lstgeq = geq.empty() ? 1 : *geq.rbegin();
        vector<int> p = {1, lstleq, lstgeq, i};
        lsort(p);
        //cerr << "p ";
        //printv(p, cerr);
        for(int j = 2; j >= 0; j--){
            if(p[j] == p[j + 1]) continue;
            vector<ll> sum(26);
            for(int k = 0; k < 26; k++){
                sum[k] = bit[k].query(p[j], p[j + 1] - 1);
                if(k) sum[k] += sum[k - 1], sum[k] %= MOD;
            }
            //cerr << "seg " << p[j] << " " << p[j + 1] - 1 << " : ";
            //printv(sum, cerr);
            for(int k = 0; k < 26; k++){
                int l = 0, r = 25;
                if(p[j] < lstleq) l = k;
                if(p[j] < lstgeq) r = k;
                ll tmp = sum[r];
                tmp -= sum[k];
                if(k) tmp += sum[k - 1];
                if(l) tmp -= sum[l - 1];
                topos(tmp);
                dp[i][k] += tmp;
                dp[i][k] %= MOD;
                //cerr << "range " << k << " : " << l << " " << r << " " << dp[i][k] << "\n";
                bit[k].modify(i, tmp);
                ans += tmp;
                ans %= MOD;
            }
        }
        //cerr << "dp " << i << " : ";
        //printv(dp[i], cerr);
    }
    cout << ans << "\n";

    return 0;
}

Compilation message

misspelling.cpp: In member function 'void BIT::modify(int, int)':
misspelling.cpp:41:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |         for(; x < bit.size(); x += lowbit(x)){
      |               ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 5 ms 980 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 2839 ms 257216 KB Output is correct
6 Correct 2837 ms 256892 KB Output is correct
7 Correct 2782 ms 257376 KB Output is correct
8 Correct 2806 ms 257228 KB Output is correct
9 Correct 2797 ms 256964 KB Output is correct
10 Correct 86 ms 10540 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 3449 ms 269208 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 5 ms 980 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 88 ms 10552 KB Output is correct
27 Correct 66 ms 10532 KB Output is correct
28 Correct 70 ms 10636 KB Output is correct
29 Correct 100 ms 10924 KB Output is correct
30 Correct 95 ms 11024 KB Output is correct
31 Correct 404 ms 32644 KB Output is correct
32 Correct 87 ms 10548 KB Output is correct
33 Correct 86 ms 10540 KB Output is correct
34 Correct 101 ms 11260 KB Output is correct
35 Correct 588 ms 42016 KB Output is correct
36 Correct 43 ms 9900 KB Output is correct
37 Correct 113 ms 10832 KB Output is correct
38 Correct 106 ms 10564 KB Output is correct
39 Correct 118 ms 10236 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 320 KB Output is correct
6 Correct 1 ms 224 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 316 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 320 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 316 KB Output is correct
19 Correct 1 ms 316 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 324 KB Output is correct
22 Correct 5 ms 980 KB Output is correct
23 Correct 1 ms 316 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 316 KB Output is correct
27 Correct 1 ms 320 KB Output is correct
28 Correct 1 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 2839 ms 257216 KB Output is correct
31 Correct 2837 ms 256892 KB Output is correct
32 Correct 2782 ms 257376 KB Output is correct
33 Correct 2806 ms 257228 KB Output is correct
34 Correct 2797 ms 256964 KB Output is correct
35 Correct 86 ms 10540 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 3449 ms 269208 KB Output is correct
39 Correct 88 ms 10552 KB Output is correct
40 Correct 66 ms 10532 KB Output is correct
41 Correct 70 ms 10636 KB Output is correct
42 Correct 100 ms 10924 KB Output is correct
43 Correct 95 ms 11024 KB Output is correct
44 Correct 404 ms 32644 KB Output is correct
45 Correct 87 ms 10548 KB Output is correct
46 Correct 86 ms 10540 KB Output is correct
47 Correct 101 ms 11260 KB Output is correct
48 Correct 588 ms 42016 KB Output is correct
49 Correct 43 ms 9900 KB Output is correct
50 Correct 113 ms 10832 KB Output is correct
51 Correct 106 ms 10564 KB Output is correct
52 Correct 118 ms 10236 KB Output is correct
53 Correct 3824 ms 254956 KB Output is correct
54 Correct 2219 ms 254596 KB Output is correct
55 Correct 3352 ms 267572 KB Output is correct
56 Correct 3352 ms 267648 KB Output is correct
57 Correct 2777 ms 257340 KB Output is correct
58 Correct 2764 ms 257484 KB Output is correct
59 Correct 2802 ms 257248 KB Output is correct
60 Correct 3768 ms 274000 KB Output is correct
61 Correct 1699 ms 235280 KB Output is correct
62 Correct 3707 ms 264496 KB Output is correct
63 Correct 3815 ms 255692 KB Output is correct
64 Correct 3804 ms 246276 KB Output is correct