Submission #379966

#	Time	Username	Problem	Language	Result	Execution time	Memory
379966		JerryLiu06	trapezoid (balkan11_trapezoid)	C++11	100 / 100	185 ms	12696 KiB

trapezoid

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

#define pb push_back

#define f first
#define s second

struct Event { int x1, x2, id, ind; bool operator<(const Event& E) { return x1 < E.x1; } };

int N; vector<Event> E; vector<int> BOT; pii tree[800010], DP[100010];

const int MOD = 30013;

int getBot(int X) { return lower_bound(BOT.begin(), BOT.end(), X) - BOT.begin() + 1; }

pii comb(pii A, pii B) { if (A.f != B.f) return max(A, B); return pii {A.f, (A.s + B.s) % MOD}; }

void update(int x, int l, int r, int pos, pii val) { int mid = (l + r) / 2;
    if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }

    update(2 * x, l, mid, pos, val); update(2 * x + 1, mid + 1, r, pos, val);

    tree[x] = comb(tree[2 * x], tree[2 * x + 1]);
}
pii query(int x, int l, int r, int tl, int tr) { int mid = (l + r) / 2;
    if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];

    return comb(query(2 * x, l, mid, tl, tr), query(2 * x + 1, mid + 1, r, tl, tr));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> N; for (int i = 0; i < N; i++) {
        int A, B, C, D; cin >> A >> B >> C >> D;

        E.pb(Event {A, C, 1, i}); E.pb(Event {B, D, -1, i});

        BOT.pb(C); BOT.pb(D);
    }
    sort(E.begin(), E.end()); sort(BOT.begin(), BOT.end());

    BOT.resize(distance(BOT.begin(), unique(BOT.begin(), BOT.end())));

    for (Event X : E) { int B = getBot(X.x2); int I = X.ind;

        if (X.id == 1) { pii CUR = query(1, 1, 2 * N, 1, B); CUR.f++; if (CUR.s == 0) CUR.s = 1; DP[I] = CUR; }

        if (X.id == -1) update(1, 1, 2 * N, B, DP[I]);
    }
    cout << tree[1].f << " " << tree[1].s << endl;
}

Compilation message (stderr)

trapezoid.cpp: In function 'void update(int, int, int, int, pii)':
trapezoid.cpp:23:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   23 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |     ^~
trapezoid.cpp:23:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   23 |     if (r < pos || l > pos) return ; if (l == r) { tree[x] = val; return ; }
      |                                      ^~
trapezoid.cpp: In function 'pii query(int, int, int, int, int)':
trapezoid.cpp:30:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   30 |     if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
      |     ^~
trapezoid.cpp:30:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   30 |     if (r < tl || l > tr) return pii {0, 0}; if (tl <= l && r <= tr) return tree[x];
      |                                              ^~

• Subtask 1: 100 / 100