Submission #561322

#	Time	Username	Problem	Language	Result	Execution time	Memory
561322		wiwiho	Misspelling (JOI22_misspelling)	C++14	100 / 100	3824 ms	274000 KiB

misspelling

#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 (stderr)

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 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11