Educational Codeforces Round 137

 

정시 파이터는 내신 전날 [코포]를 한다~~

D 제출 직후!!

잘 봤다!

4솔 직후 오렌지 퍼포가 떴는데, 대회 종로 40분 전쯤까지 오렌지 퍼포가 유지됐다.

 

E를 보다가 케이스 분류가 상당히 많을 것 같다는 직감이 들어서 F로 넘어갈까 생각을 했다. 그래서 푼 사람 수를 확인했더니 30:40 정도 됐나 그래서 확실하게 접고 넘어갔다.

 

F는 대충 풀이가 나오긴 했는데 자꾸 에러 뜨고 컴파일이 매우 느려져서 뭔가 vsc도 안 돌고 막 그러다가 끝났다.

 

 

A. 살짝 오래 걸리긴 했는데, WA는 안 받아서 모난 데 없이 잘 푼 것 같다.

 

B. 2분만에 풀었으니 적당한 속도로 잘 풀었다. 이 또한 모난 데 없다.

 

C. 얘는 꽤 오래 걸렸다. 처음에 그리디 풀이가 예제에서 반례가 나와서 지우고 다시 짜느라 그런 것 같다. 이는 충분히 분석을 안 하고 임한 탓이다. 아무튼 그래서 [01…1] 단위로 끊는 조금 확장한 그리디 풀이로 WA 없이 통과했다.

결국 그리디 풀이는 항상 반례를 고민하면서 구상해야 하는데 이를 놓친게 문제라고 본다. 반성하자.

 

D. 최근에 랜덤 알고리즘을 공부해서 너무 날로 먹어버렸다. 여기서 퍼포먼스가 확 뒤집혔다. 이때부터 끝나기 30분 전까지 친창 1위를 유지할 수 있었다..!!

처음에는 하나 고정하고 나머지 하나를 옆으로 움직이면서 하면 되겠다는 관찰을 잘 했다. 그리곤 이상한 그리디를 하다가 예제에서 반례가 나왔다.

역시 그리디를 구상할 때 반례를 충분히 고민 안 했다…

근데 이제 문제의 랜덤 조건을 보아하니 1로 이뤄진 suffix의 길이가 reasonable하게 작겠다는 생각이 들었고, 이미 써둔 코드를 약간만 수정해서 바로 맞출 수 있었다.

 

E. 업솔빙 계획 있음

F. 업솔빙 완료. [0,3e5]인데, [1,3e5]에만 반복해서 틀렸다.

#pragma region candidate!candidate!candidate!candidate!
// g++-11 -std=c++17 -O2 -Wall -Wno-unknown-pragmas -DLOCAL
#include <bits/stdc++.h>
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define siz(x) int(x.size())
#define dbg(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define F first
#define S second
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>; constexpr int floor_log2(int x) { assert(x > 0); return 31-__builtin_clz(x) ;} constexpr int ceil_log2(int x) { assert(x > 0); return 31-__builtin_clz(x)+bool(x&(x-1)); } constexpr ll floor(ll p, ll q) { return p/q-((p^q) < 0 and p%q); } constexpr ll ceil(ll p, ll q) { return p/q+((p^q) > 0 and p%q); } string to_string(string s) { return '"'+s+'"'; } string to_string(bool b) { return b ? "true" : "false"; } template <typename A,typename B> string to_string(pair<A,B> p) { return "("+to_string(p.F)+", "+to_string(p.S)+")"; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) res += ", "; first = false; res += to_string(x); } res += "}"; return res; } void debug_out() { cerr << endl; } template <typename Head,typename... Tail> void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); } void precalc(); void solution(int); int main() {cin.tie(0)->sync_with_stdio(0); precalc(); solution(1);}
#pragma endregion

#define FC(a) [](const auto &x, const auto &y){return a;}

void precalc() {}

#pragma region modnum template from ecnerwala/cp-book ...
using mint = modnum<998244353>;

mint pw(mint x, ll e) {
    mint r = 1;
    while (e > 0) {
        if (e%2) r *= x;
        e /= 2, x *= x;
    }
    return r;
}

template <typename T, const int N>
struct RUPQ {
    T t[2*N]; function<T(const T&,const T&)> op;
    RUPQ(T e, function<T(const T&,const T&)> f): op(f) { fill(t,t+2*N,e); }
    T &operator [] (int i) { return t[N+i]; }
    void clear() { fill(t,t+2*N,t[0]); }
    void push() {
        for (int k = 1; k < N; ++k) {
            t[2*k] = op(t[2*k],t[k]);
            t[2*k+1] = op(t[2*k+1],t[k]);
            t[k] = t[0];
        }
    }
    void update(int a, int b, const T &v) {
        assert(0 <= a and a < N and 0 <= b and b < N);
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) t[a] = op(t[a],v);
            if (~b&1) t[b] = op(t[b],v);
        }
    }
    T query(int k) {
        assert(0 <= k and k < N);
        T s = t[0];
        for (k += N; k >= 1; k /= 2)
            s = op(s,t[k]);
        return s;
    }
};

const int N = 3e5+3;
int n;
RUPQ<int,N> ds(-1,FC(max(x,y)));

void solution(int tc) {
    cin >> n;
    rep(i,1,n) {
        int s, e; cin >> s >> e;
        ds.update(s,e,i-1);
    }
    ds.push(); mint ans = 0;
    rep(i,0,int(3e5)) if (ds[i] != -1) {
        mint v;
        if (ds[i] == 0) v = pw(2,n-1-ds[i]);
        else v = pw(3,ds[i]-1)*pw(2,n-ds[i]);
        ans += v;
    }
    cout << ans;
}