CF1642

A. Hard Way

没有读懂题。

一个三角形合法当且仅当为一个倒三角，且最上面的一条边水平。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> PII;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        PII a[3];
        for (int i = 0; i < 3; i++)
            cin >> a[i].second >> a[i].first;
        sort(a, a + 3);
        if (a[1].first == a[2].first)
            cout << a[2].second - a[1].second << endl;
        else
            cout << 0 << endl;
    }
    return 0;
}

B. Power Walking

求多少个不同的数。

千万不要用 unordered_map ，赛时想 Hack 一个人，把他卡成了 $3s$ ，但是文件太大交不了。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n;
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n;
        set<int> s;
        for (int i = 1, a; i <= n; i++)
        {
            cin >> a;
            s.insert(a);
        }
        int t = s.size();
        for (int k = 1; k <= n; k++)
            cout << max(k, t) << ' ';
        cout << endl;
    }
    return 0;
}

C. Great Sequence

如果两个数一个是另一个的 $k$ 倍，那么可以消去这两个数，求最后还剩多少个数。

可以直接用 set 搞，但是我感觉 STL 不靠谱，就写了双指针。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
bool vis[N];
int n;
LL k, w[N];
int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        cin >> n >> k;
        for (int i = 0; i < n; i++)
            cin >> w[i];
        sort(w, w + n);
        int res = n;
        for (int i = 0, j = 1; i < n; i++)
        {
            if (vis[i])
                continue;
            while (j < n && w[i] * k > w[j])
                j++;
            if (j == n)
                break;
            if (w[i] * k == w[j])
            {
                vis[j++] = true;
                res -= 2;
            }
        }
        for (int i = 0; i < n; i++)
            vis[i] = false;
        cout << res << endl;
    }
    return 0;
}

E. Anonymity Is Important

用 set 维护现在还不是病人的点，对于一个 $x$ ，前驱为 $l$ ，后继 $r$ ，如果存在一段有病人的区间 $[a, b]$ 满足 $a \in (l, x) , b \in (x, r)$ ，那么 $x$ 是病人。

线段树维护区间最小值，每个位置 $a$ 的值表示最小的区间 $[a, b]$ 的 $b$ 。

查看代码

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
template <class Type>
void chkmin (Type &x, Type k)
{
    k < x && (x = k);
}
const int N = 2e5 + 10;
int n, m, tr[N << 2];
set <int> s;
void build (int l = 1, int r = n, int x = 1)
{
    tr[x] = n + 1;
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(l, mid, x << 1), build(mid + 1, r, x << 1 | 1);
}
void modify (int t, int k, int l = 1, int r = n, int x = 1)
{
    chkmin(tr[x], k);
    if (l == r)
        return;
    int mid = l + r >> 1;
    t <= mid ? modify(t, k, l, mid, x << 1) : modify(t, k, mid + 1, r, x << 1 | 1);
}
int query (int L, int R, int l = 1, int r = n, int x = 1)
{
    if (l > R || L > r)
        return n + 1;
    if (l >= L && r <= R)
        return tr[x];
    int mid = l + r >> 1;
    return min(query(L, R, l, mid, x << 1), query(L, R, mid + 1, r, x << 1 | 1));
}
int main ()
{
    read(n), read(m);
    build();
    for (int i = 0; i <= n + 1; i++)
        s.insert(i);
    for (int op; m; m--)
    {
        read(op);
        if (op == 0)
        {
            int l, r, x;
            read(l), read(r), read(x);
            if (x == 0)
                for (auto i = s.lower_bound(l); i != s.end() && *i <= r; i = s.erase(i));
            else if (x == 1)
                modify(l, r);
        }
        else if (op == 1)
        {
            int x;
            read(x);
            puts(s.count(x) ? (query(*--s.lower_bound(x) + 1, x) < *s.upper_bound(x) ? "YES" : "N/A") : "NO");
        }
    }
    return 0;
}