2018-2019 ACM-ICPC, Asia Seoul Regional Contest

先吐槽一下…不知道是不是药的副作用（明明我听说的副作用是失眠啊），9点起床到了11点半巨困，睡到两点，勉强起来写了道签到题D，然后看了下A比较眼熟就开始做A。写着写着又犯困…第一次提交是RE，迷迷糊糊地改成WA了以后实在撑不住趴电脑上睡着了。晚上清醒了再看发现是非常sb的错误，好无语啊！

A. Circuits

Problem

给你两条水平直线和平面上许多矩形，问两条横线最多能穿过几个矩形（被重复穿过只算一次）。

Constraints

• \[3\leq n\leq 10^5\]
• \[−10^{-7} ≤ u_x, u_y, v_x, v_y ≤ 10^7\]

Reason

• 第一眼看到就想起了之前做过的Contamination(2020 Petrozavodsk Winter Camp, Jagiellonian U Contest)，也是线段树+扫描线+离散化。横坐标没有用，直接看纵坐标\(y_{min}\)和\(y_{max}\). 对于每个矩形在\(y_{min}\)处激活，在\(y_{max}\)处失效。遍历一下第一条横线的位置然后用线段树求第二条横线能加几个就行了。
• 每个矩阵对应两个纵坐标嘛，所以MAXN = 2e5
• 然而我犯了非常sb的错误…把线段树模版的root * 2改成root << 2了，导致WA，我是sb

Solution

#include <algorithm>
#include <climits>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define LL long long

const int MAXN = 2e5 + 5;

struct R {
    int minn;
    int maxx;
};

struct Node {
    int pos;
    R y;
    int op;
    friend bool operator<(Node x, Node y) {
        return x.pos != y.pos ? x.pos < y.pos : x.op < y.op;
    }
} a[MAXN];

vector<int> ys; // 离散化

int tree[MAXN << 2];
int lazy[MAXN << 2];

inline void maintain(int cl, int cr, int p) {
    if (lazy[p]) {
        lazy[p << 1] += lazy[p];
        lazy[p << 1 | 1] += lazy[p];
        tree[p << 1] += lazy[p];
        tree[p << 1 | 1] += lazy[p];
        lazy[p] = 0;
    }
}

inline int query() { return max(0, tree[1]); }

inline void modify(int l, int r, int cl, int cr, int root) {
    if (l <= cl && cr <= r) {
        tree[root] += 1;
        lazy[root] += 1;
        return;
    }
    maintain(cl, cr, root);
    int m = cl + (cr - cl) / 2;
    if (l <= m)
        modify(l, r, cl, m, root << 1);
    if (r > m)
        modify(l, r, m + 1, cr, (root << 1) | 1);
    tree[root] = max(tree[root << 1], tree[(root << 1) | 1]);
}

inline void build(int left, int right, int root) {
    tree[root] = 0;
    lazy[root] = 0;
    if (left == right) {
        return;
    }
    int m = left + ((right - left) >> 1);
    build(left, m, root << 1);
    build(m + 1, right, (root << 1) | 1);
}

void solve() {
    int n;
    cin >> n;

    int cnt = 0;

    for (int i = 1; i <= n; i++) {
        int ux, uy, vx, vy;
        cin >> ux >> uy >> vx >> vy;
        uy++;
        a[++cnt] = {vy, {vy, uy}, 1};
        a[++cnt] = {uy, {vy, uy}, -1};
        ys.push_back(vy);
        ys.push_back(uy);
    }

    sort(a + 1, a + cnt + 1);

    sort(ys.begin(), ys.end());
    ys.erase(unique(ys.begin(), ys.end()), ys.end());
    for (int i = 1; i <= cnt; i++) {
        a[i].y.maxx =
            lower_bound(ys.begin(), ys.end(), a[i].y.maxx) - ys.begin() + 1;
        a[i].y.minn =
            lower_bound(ys.begin(), ys.end(), a[i].y.minn) - ys.begin() + 1;
    }

    build(1, 1, ys.size());
    LL s = 0;
    LL res = 0;
    for (int i = 1; i <= cnt; i++) {
        s += a[i].op;
        res = max(res, s + query());

        if (a[i].op == -1)
            modify(a[i].y.minn, a[i].y.maxx - 1, 1, ys.size(), 1);
    }
    cout << res << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}

D. Go Latin

纯纯签到题，没什么好说的

Solution

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    if (s[n - 1] == 'a' || s[n - 1] == 'o' || s[n - 1] == 'u')
        cout << s + "s" << endl;
    else if (s[n - 1] == 'i' || s[n - 1] == 'y')
        cout << s.substr(0, n - 1) + "ios" << endl;
    else if (s[n - 1] == 'l' || s[n - 1] == 'r' || s[n - 1] == 'v')
        cout << s + "es" << endl;
    else if (s[n - 1] == 'n')
        cout << s.substr(0, n - 1) + "anes" << endl;
    else if (s[n - 1] == 'e' && s[n - 2] == 'n')
        cout << s.substr(0, n - 2) + "anes" << endl;
    else if (s[n - 1] == 't' || s[n - 1] == 'w')
        cout << s + "as" << endl;
    else
        cout << s + "us" << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}