답안 #242916

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242916 2020-06-29T19:21:49 Z ant101 사다리꼴 (balkan11_trapezoid) C++14
100 / 100
448 ms 28664 KB
#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 30013; // 998244353; // = (119<<23)+1
const int MX = 1e5+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};


namespace io {
    void setIn(string s) { freopen(s.c_str(),"r",stdin); }
    void setOut(string s) { freopen(s.c_str(),"w",stdout); }
    void setIO(string s = "") {
        ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
        // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
        if (sz(s)) {
            setIn(s+".in");
            setOut(s+".out");
        } // for USACO
    }
}

using namespace io;

namespace input {
    template<class T> void re(complex<T>& x);
    template<class T1, class T2> void re(pair<T1,T2>& p);
    template<class T> void re(vector<T>& a);
    template<class T, size_t SZ> void re(array<T,SZ>& a);
    
    template<class T> void re(T& x) { cin >> x; }
    void re(double& x) { string t; re(t); x = stod(t); }
    void re(ld& x) { string t; re(t); x = stold(t); }
    template<class Arg, class... Args> void re(Arg& first, Args&... rest) {
        re(first); re(rest...);
    }
    
    template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
    template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
    template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
    template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

namespace output {
    template<class T1, class T2> void pr(const pair<T1,T2>& x);
    template<class T, size_t SZ> void pr(const array<T,SZ>& x);
    template<class T> void pr(const vector<T>& x);
    template<class T> void pr(const set<T>& x);
    template<class T1, class T2> void pr(const map<T1,T2>& x);
    
    template<class T> void pr(const T& x) { cout << x; }
    template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) {
        pr(first); pr(rest...);
    }
    
    template<class T1, class T2> void pr(const pair<T1,T2>& x) {
        pr("{",x.f,", ",x.s,"}");
    }
    template<class T> void prContain(const T& x) {
        pr("{");
        bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool>
        pr("}");
    }
    template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); }
    template<class T> void pr(const vector<T>& x) { prContain(x); }
    template<class T> void pr(const set<T>& x) { prContain(x); }
    template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); }
    
    void ps() { pr("\n"); }
    template<class Arg> void ps(const Arg& first) {
        pr(first); ps(); // no space at end of line
    }
    template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) {
        pr(first," "); ps(rest...); // print w/ spaces
    }
}

using namespace output;

using namespace input;

int add(int a, int b) {
    a += b;
    if(a >= MOD) {
        a -= MOD;
    }
    return a;
}
int sub(int a, int b) {
    a -= b;
    if(a < 0) {
        a += MOD;
    }
    return a;
}

int mul(int a, int b) {
    return (a * b)%MOD;
}

void add_self(int& a, int b) {
    a = add(a, b);
}
void sub_self(int& a, int b) {
    a = sub(a, b);
}
void mul_self(int& a, int b) {
    a = mul(a, b);
}



int N, M = 0;

struct T {
    int tl, tr, bl, br;
};

bool cmp(T a, T b) {return a.bl<b.bl;}

map<int, int> cc;

T trap[MX];
int t[MX*16];
int dp[MX];
pair<pair<int, int>, int> events[MX*2];
vector<int> inds[MX];
vector<int> trees[MX];
int dp2[MX];

void update(ll ind, ll num, ll dval) {
    while (ind<=trees[dval].size()) {
        add_self(trees[dval][ind-1], num);
        ind+=(ind&-ind);
    }
}

ll getsum(ll ind, ll dval) {
    if (ind == 0) {
        return 0;
    }
    int sum = 0;
    while (ind) {
        add_self(sum, trees[dval][ind-1]);
        ind-=(ind&-ind);
    }
    return sum;
}

void upd(ll curr, ll tl, ll tr, ll pos, ll val) {
    if (tl == tr && tl == pos) {
        t[curr] = val;
    } else {
        ll tm = (tl+tr)/2;
        if (pos <= tm) {
            upd(curr*2, tl, tm, pos, val);
        } else {
            upd(curr*2+1, tm+1, tr, pos, val);
        }
        t[curr] = max(t[curr*2], t[curr*2+1]);
    }
}

ll qry(ll curr, ll tl, ll tr, ll l, ll r) {
    if (l > r) {
        return 0;
    }
    if (tl == l && tr == r) {
        return t[curr];
    } else {
        ll tm = (tl+tr)/2;
        return max(qry(curr*2, tl, tm, l, min(r, tm)), qry(curr*2+1, tm+1, tr, max(l, tm+1), r));
    }
}

int main() {
    setIO();
    re(N);
    FOR (i, 1, N+1) {
        re(trap[i].tl, trap[i].tr, trap[i].bl, trap[i].br);
    }
    sort(trap+1, trap+1+N, cmp);
    FOR (i, 1, N+1) {
        cc[trap[i].tl] = 0;
        cc[trap[i].tr] = 0;
        cc[trap[i].bl] = 0;
        cc[trap[i].br] = 0;
    }
    ll curr = 0;
    trav (i, cc) {
        cc[i.f] = ++curr;
    }
    FOR (i, 1, N+1) {
        trap[i].tl = cc[trap[i].tl];
        trap[i].tr = cc[trap[i].tr];
        trap[i].bl = cc[trap[i].bl];
        trap[i].br = cc[trap[i].br];
    }
    cc.clear();
    FOR (i, 1, N+1) {
        events[++M] = {{trap[i].tr, trap[i].br}, i};
        events[++M] = {{trap[i].tl, trap[i].bl}, i};
    }
    sort(events+1, events+1+M);
    int best = 1;
    ROF (i, 1, M+1) {
        ll ind = events[i].s;
        if (events[i].f == mp(trap[ind].tr, trap[ind].br)) {
            dp[ind] = 1+qry(1, 1, curr, trap[ind].br, curr);
            best = max(best, dp[ind]);
        } else {
            upd(1, 1, curr, trap[ind].bl, dp[ind]);
        }
    }
    FOR (i, 1, N+1) {
        inds[dp[i]].push_back(trap[i].bl);
    }
    FOR (i, 1, N+1) {
        if (inds[i].size()) {
            vector<int> v(inds[i].size(), 0);
            trees[i] = v;
        }
    }
    ROF (i, 1, M+1) {
        ll ind = events[i].s;
        if (events[i].f == mp(trap[ind].tr, trap[ind].br)) {
            ll lnum = dp[ind]-1;
            if (lnum == 0) {
                dp2[ind] = 1;
                continue;
            }
            auto vil = lower_bound(inds[lnum].begin(), inds[lnum].end(), trap[ind].br);
            dp2[ind] = sub(getsum(inds[lnum].size(), lnum), getsum(distance(inds[lnum].begin(), vil), lnum));
        } else {
            auto vil = lower_bound(inds[dp[ind]].begin(), inds[dp[ind]].end(), trap[ind].bl);
            update(distance(inds[dp[ind]].begin(), vil)+1, dp2[ind], dp[ind]);
        }
    }
    int ans = 0;
    FOR (i, 1, N+1) {
        if (dp[i] == best) {
            add_self(ans, dp2[i]);
        }
    }
    ps(best, ans);
    return 0;
}

Compilation message

trapezoid.cpp: In function 'void update(ll, ll, ll)':
trapezoid.cpp:188:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ind<=trees[dval].size()) {
            ~~~^~~~~~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'void io::setIn(std::__cxx11::string)':
trapezoid.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
trapezoid.cpp: In function 'void io::setOut(std::__cxx11::string)':
trapezoid.cpp:68:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 4992 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5120 KB Output is correct
4 Correct 9 ms 5248 KB Output is correct
5 Correct 12 ms 5504 KB Output is correct
6 Correct 15 ms 5888 KB Output is correct
7 Correct 15 ms 5632 KB Output is correct
8 Correct 21 ms 6144 KB Output is correct
9 Correct 36 ms 7544 KB Output is correct
10 Correct 50 ms 8316 KB Output is correct
11 Correct 82 ms 11384 KB Output is correct
12 Correct 193 ms 17784 KB Output is correct
13 Correct 234 ms 19832 KB Output is correct
14 Correct 288 ms 24824 KB Output is correct
15 Correct 320 ms 21240 KB Output is correct
16 Correct 401 ms 22392 KB Output is correct
17 Correct 373 ms 27004 KB Output is correct
18 Correct 220 ms 19832 KB Output is correct
19 Correct 360 ms 27896 KB Output is correct
20 Correct 448 ms 28664 KB Output is correct