Submission #1042737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042737		c2zi6	Teams (IOI15_teams)	C++14	21 / 100	4022 ms	20960 KiB

teams

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<typename T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "teams.h"

/* PERSISTENT SEGMENT TREE FOR 2D SUM QUERIES */
struct PERSISTENTSEGTREE {
    static const int MININD = 0;
    static const int MAXIND = 1000;
    VI val;
    VI lft, rgt;
    VI roots;
    VI layer;
    int addnode() {
        val.pb(0);
        lft.pb(0);
        rgt.pb(0);
        return val.size()-1;
    }
    PERSISTENTSEGTREE() {
        roots.pb(addnode());
        layer.pb(-1e9);
    }
    void upd(int PREV, int N, int L, int R, int i, int s) {
        if (L == R) {
            if (PREV == -1) val[N] = s;
            else val[N] = val[PREV] + s;
            return;
        }
        int M = (L + R) / 2;
        if (i <= M) {
            if (!lft[N]) lft[N] = addnode();
            upd(lft[PREV], lft[N], L, M, i, s);
            rgt[N] = rgt[PREV];
        } else {
            if (!rgt[N]) rgt[N] = addnode();
            upd(rgt[PREV], rgt[N], M+1, R, i, s);
            lft[N] = lft[PREV];
        }
        val[N] = val[lft[N]] + val[rgt[N]];
    }
    void upd(int time, int ind, int s = +1) {
        roots.pb(addnode());
        layer.pb(time);
        upd(roots[roots.size()-2], roots[roots.size()-1], MININD, MAXIND, ind, s);
    }
    int get(int N, int L, int R, int l, int r) {
        if (l <= L && R <= r) return val[N];
        if (R < l || L > r) return 0;
        int M = (L + R) / 2;
        int sum = 0;
        if (lft[N]) sum += get(lft[N], L, M, l, r);
        if (rgt[N]) sum += get(rgt[N], M+1, R, l, r);
        return sum;
    }
    int get(int time, int l, int r) {
        return get(roots[upper_bound(all(layer), time) - layer.begin()-1], MININD, MAXIND, l, r);
    }
};
struct PURS {
    /*PERSISTENTSEGTREE seg;*/
    int bit[1000][1000];
    void add(int i, int j) {
        for (int ii = i; ii < 1000; ii += ii&-ii) {
            for (int jj = j; jj < 1000; jj += jj&-jj) {
                bit[ii][jj]++;
            }
        }
    }
    int get(int i, int j) {
        int ret = 0;
        for (int ii = i; ii > 0; ii -= ii&-ii) {
            for (int jj = j; jj > 0; jj -= jj&-jj) {
                ret += bit[ii][jj];
            }
        }
        return ret;
    }
    PURS(){}
    PURS(VPI a) {
        for (auto&[x, y] : a) swap(x, y);
        sort(all(a));
        /*for (auto[x, y] : a) seg.upd(x, y);*/
        rep(i, 1000) rep(j, 1000) bit[i][j] = 0;
        for (auto[x, y] : a) add(x, y);
    }
    int get(int minx, int maxx, int miny, int maxy) {
        return get(maxx, maxy) - get(minx-1, maxy) - get(maxx, miny-1) + get(minx-1, miny-1);
        /*int ret;*/
        /*if (maxy < miny) ret = 0;*/
        /*else ret = seg.get(maxx, miny, maxy) - seg.get(minx-1, miny, maxy);*/
        /*return ret;*/
    }
};

int n;
VPI ranges;
PURS table;

void init(int N, int A[], int B[]) {
    n = N;
    ranges = VPI(n);
    rep(i, n) ranges[i] = {A[i], B[i]};
    table = PURS(ranges);
    sort(all(ranges));
}

int can(int M, int K[]) {
    int m = M;
    VI a(m);
    rep(i, m) a[i] = K[i];
    sort(all(a));

    auto solve1 = [&]() {
        VI dp(m);
        rep(i, m) {
            /*dp[i] = table.get(a[i], +1e9, 0, a[i]) - a[i];*/
            dp[i] = table.get(a[i], 999, 1, a[i]) - a[i];
            rep(j, i) {
                /*setmin(dp[i], dp[j] + table.get(a[i], +1e9, a[j]+1, a[i]) - a[i]);*/
                setmin(dp[i], dp[j] + table.get(a[i], 999, a[j]+1, a[i]) - a[i]);
            }
        }
        int mn = 2e9;
        for (int x : dp) setmin(mn, x);
        return mn >= 0;
    };
    auto solve2 = [&]() {
        multiset<int> ms;
        int rpt = 0;
        for (int cur : a) {
            while (rpt != ranges.size() && ranges[rpt].ff <= cur) {
                ms.insert(ranges[rpt++].ss);
            }
            auto it = ms.lower_bound(cur);
            while (cur--) {
                if (it == ms.end()) return false;
                it++;
                ms.erase(prev(it));
            }
        }
        return true;
    };
    return solve1();
    /*int ans1 = solve1();*/
    /*int ans2 = solve2();*/
    /*cout << ans1 << " " << ans2 << "\n";*/
    /*if (ans1 != ans2) {*/
    /*    cout << n << endl;*/
    /*    rep(i, n) cout << ranges[i].ff << " " << ranges[i].ss << endl;*/
    /*    cout << m << endl;*/
    /*    for (int x : a) cout << x << " ";*/
    /*    cout << endl;*/
    /*    abort();*/
    /*}*/
    return -1;
}

Compilation message (stderr)

teams.cpp: In member function 'int PERSISTENTSEGTREE::addnode()':
teams.cpp:46:26: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   46 |         return val.size()-1;
      |                ~~~~~~~~~~^~
teams.cpp: In constructor 'PURS::PURS(VPI)':
teams.cpp:109:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         for (auto&[x, y] : a) swap(x, y);
      |                   ^
teams.cpp:113:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  113 |         for (auto[x, y] : a) add(x, y);
      |                  ^
teams.cpp: In lambda function:
teams.cpp:160:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |             while (rpt != ranges.size() && ranges[rpt].ff <= cur) {
      |                    ~~~~^~~~~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:156:10: warning: variable 'solve2' set but not used [-Wunused-but-set-variable]
  156 |     auto solve2 = [&]() {
      |          ^~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 0 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23