Submission #417711

#	Time	Username	Problem	Language	Result	Execution time	Memory
417711		MarcoMeijer	trapezoid (balkan11_trapezoid)	C++14	100 / 100	229 ms	49468 KiB

trapezoid

#include <bits/stdc++.h>
using namespace std;
 
// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e18
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }
 
// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const vector<T>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class T> void OUT(const vector<T>& x) {RE(i,x.size()) OUT(i==0?"":" ",x[i]);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }
 
// dp
template<class T> bool ckmin(T&a, T&b) { bool bl = a > b; a = min(a,b); return bl;}
template<class T> bool ckmax(T&a, T&b) { bool bl = a < b; a = max(a,b); return bl;}
 
void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}
 
 
//===================//
//   begin program   //
//===================//
 
const int MX = 5e5;
const int N = (1<<20);
const int MOD = 30013;

int n;
int a[MX], b[MX], c[MX], d[MX];

// fenwick tree
int FT[MX];
void addFT(int i, int value) {
    for(i++; i<MX; i+=i&-i) FT[i] = max(FT[i],value);
}
int getFT(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans = max(ans, FT[i]);
    return ans;
}
int SM[MX];
void addSM(int i, int value) {
    for(i++; i<MX; i+=i&-i) SM[i] = (SM[i]+value)%MOD;
}
int getSM(int i) {
    int ans = 0;
    for(i++; i; i-=i&-i) ans = (ans+SM[i])%MOD;
    return ans;
}

// lis
int lis[MX];
vi atA[MX], atB[MX];
vi layer[MX];
int dp[MX];

void program() {
    IN(n);
    RE(i,n) IN(a[i],b[i],c[i],d[i]);

    // coordinate compression
    vi difx;
    RE(i,n) difx.pb(a[i]), difx.pb(b[i]), difx.pb(c[i]), difx.pb(d[i]);
    sort(all(difx));
    RE(i,n) {
        a[i] = lower_bound(all(difx),a[i]) - difx.begin();
        b[i] = lower_bound(all(difx),b[i]) - difx.begin();
        c[i] = lower_bound(all(difx),c[i]) - difx.begin();
        d[i] = lower_bound(all(difx),d[i]) - difx.begin();
    }

    // getting lis
    RE(i,n) atA[a[i]].pb(i);
    RE(i,n) atB[b[i]].pb(i);
    RE(i,n*4) {
        FOR(j,atA[i])
            lis[j] = getFT(c[j]-1) + 1;
        FOR(j,atB[i])
            addFT(d[j], lis[j]);
    }

    // getting dp
    RE(i,n) layer[lis[i]].pb(i);
    RE1(i,n) {
        priority_queue<iii,viii,greater<iii>> pq;
        FOR(j,layer[i-1])
            pq.push({b[j],2,j});
        FOR(j,layer[i])
            pq.push({a[j],1,j});
        while(!pq.empty()) {
            iii p = pq.top(); pq.pop();
            int x, t, j;
            tie(x,t,j) = p;
            if(t == 1) {
                dp[j] = getSM(c[j]-1);
                if(i == 1)
                    dp[j] = 1;
            }
            if(t == 2)
                addSM(d[j], dp[j]);
        }
        FOR(j,layer[i-1])
            addSM(d[j],-dp[j]);
    }

    int ans=0, ans2=0;
    RE(i,n) ans = max(ans,lis[i]);
    RE(i,n) if(lis[i] == ans) ans2=(ans2+dp[i])%MOD;
    OUTLS(ans,ans2);
}

• Subtask 1: 100 / 100