oj.uz

Submission #417710

# Submission time Handle Problem Language Result Execution time Memory
417710 2021-06-04T07:42:25 Z MarcoMeijer trapezoid (balkan11_trapezoid) C++14
52 / 100
 235 ms 49404 KB 
#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+=dp[i];
    OUTLS(ans,ans2);
}

Subtask #1
52.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 35660 KB Output is correct
2 Correct 24 ms 35660 KB Output is correct
3 Partially correct 25 ms 35652 KB Partially correct
4 Partially correct 25 ms 35788 KB Partially correct
5 Correct 28 ms 35868 KB Output is correct
6 Partially correct 35 ms 35964 KB Partially correct
7 Partially correct 33 ms 36164 KB Partially correct
8 Partially correct 37 ms 36392 KB Partially correct
9 Partially correct 42 ms 36944 KB Partially correct
10 Partially correct 59 ms 38412 KB Partially correct
11 Partially correct 69 ms 39056 KB Partially correct
12 Partially correct 122 ms 42176 KB Partially correct
13 Correct 146 ms 43936 KB Output is correct
14 Partially correct 169 ms 45392 KB Partially correct
15 Partially correct 181 ms 45996 KB Partially correct
16 Partially correct 202 ms 46976 KB Partially correct
17 Partially correct 204 ms 47620 KB Partially correct
18 Partially correct 196 ms 48184 KB Partially correct
19 Partially correct 232 ms 48612 KB Partially correct
20 Partially correct 235 ms 49404 KB Partially correct