oj.uz

답안 #297450

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
297450 2020-09-11T14:55:29 Z ToMmyDong 팀들 (IOI15_teams) C++17
100 / 100
 1345 ms 496920 KB 
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) static_cast<int>(i.size())
#define FOR(i, j, k, in) for (int i=j; i < (k) ; i+=in)
#define RFOR(i, j, k, in) for (int i=j; i >= (k) ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i, j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(), _a.end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define X first
#define Y second
template<typename T, typename S>
istream &operator >> (istream &is, pair<T, S> &p) {
    return is >> p.X >> p.Y;
}
#ifdef tmd
#define TIME(i) Timer i(#i)
#define debug(...) do {\
    fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
    _do(__VA_ARGS__);\
}while(0)
template<typename T> void _do(T &&_x) {cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x, S &&..._t) {cerr <<_x <<" ,"; _do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s, const pair<_a, _b> &_p) {return _s << "(" << _p.X << "," << _p.Y << ")";}
template<typename It> ostream& _OUTC(ostream &_s, It _ita, It _itb)
{
    _s << "{";
    for (It _it=_ita; _it != _itb; _it++) {
        _s <<(_it == _ita?"":",")<< *_it;
    }
    _s << "}";
    return _s;
}
template<typename _a> ostream &operator << (ostream &_s, const vector<_a> &_c) {return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,2> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,3> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,4> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const array<_a,5> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const set<_a> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s, const deque<_a> &_c) {return _OUTC(_s, ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s, const map<_a,_b> &_c) {return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
class Timer {
private:
    string scope_name;
    chrono::high_resolution_clock::time_point start_time;
public:
    Timer (string name) : scope_name(name) {
        start_time = chrono::high_resolution_clock::now();
    }
    ~Timer () {
        auto stop_time = chrono::high_resolution_clock::now();
        auto length = chrono::duration_cast<chrono::microseconds>(stop_time - start_time).count();
        double mlength = double(length) * 0.001;
        debug(scope_name, mlength);
    }
};
#else
#define TIME(i)
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif
#include "teams.h"

const int MAXN = 500005;
int n;

struct Node {
    Node *lc, *rc;
    int sz;
    Node ():lc(0), rc(0), sz(0) {}
};
Node mem[MAXN*40], *root[MAXN];
int node_cnt;

Node* get_new () {
    return &mem[node_cnt++];
}

Node* get_new (Node *nd) {
    mem[node_cnt] = *nd;
    return &mem[node_cnt++];
}

Node *build (int l, int r) {
    if (r == l + 1) {
        return get_new();
    }
    int m = (l + r) >> 1;
    Node *nd = get_new();
    nd->lc = build(l, m);
    nd->rc = build(m, r);
    return nd;
}

Node *ins (int nL, int nR, int *elm, int sz, Node *nd) {
    Node *res = get_new(nd);
    res->sz += sz;
    if (nL < nR-1) {
        int nM = (nL + nR) >> 1;
        int ls = lower_bound(elm, elm+sz, nM) - elm;
        if (ls) res->lc = ins(nL, nM, elm, ls, res->lc);
        if (sz-ls) res->rc = ins(nM, nR, elm+ls, sz-ls, res->rc);
    }
    return res;
}

int qry (int nL, int nR, int x, Node *nd) {
    if (x <= nL) return nd->sz;
    if (x >= nR) return 0;
    int nM = (nL + nR) >> 1;
    return qry(nL, nM, x, nd->lc) + qry(nM, nR, x, nd->rc);
}

int qry(Node* lnd, Node *rnd, int x) {
    int res = qry(1, n+1, x, rnd) - qry(1, n+1, x, lnd);
    return res;
}

int cur[MAXN];
vector<pii> rng;
void init(int N, int A[], int B[]) {
    n = N;
    for (int i=0; i<n; i++) {
        rng.eb(A[i], B[i]);
    }
    sort(ALL(rng));
    root[0] = build(1, n+1);
    for (int i=1, j=0, sz=0; i<=n; i++) {
        root[i] = root[i-1];
        while (j<n && rng[j].X == i) {
            cur[sz++] = rng[j++].Y;
        }
        if (sz) root[i] = ins(1, n+1, cur, sz, root[i]);
        sz = 0;
    }
}

struct Line {
    int i, l, r;
};
int *k, dp[MAXN];;
int tran (int f, int t) {
    debug(f, t);
    return dp[f] - k[t-1] + qry(root[f?k[f-1]:0], root[k[t-1]], k[t-1]);
}

int m;
int cut (int a, int b) {
    // max x s.t. f(a,x) < f(b,x)
    int L = max(a,b), R = m + 1;
    while (L < R - 1) {
        int M = (L + R) >> 1;
        if (tran(a,M) < tran(b,M)) L = M;
        else R = M;
    }
    return L;
}

int can(int M, int K[]) {
    m = M;
    sort(K, K+M);
    k = K;
    dp[0] = 0;

    deque<Line> deq;
    deq.pb({0, 1, M});
    for (int i=1; i<=M; i++) {
        // query
        while (deq.back().r < i) deq.pop_back();
        assert(deq.size());
        dp[i] = tran(deq.back().i, i);
#ifdef tmd
        int chk = tran(0, i);
        for (int j=1; j<i; j++) chk=min(chk, tran(j,i));
        assert(chk == dp[i]);
#endif

        while(deq.size() && tran(i, deq.back().r) < tran(deq.back().i, deq.back().r)) deq.pop_back();
        Line nw = Line{i, i+1, M};
        if (deq.size()) {
            int c = cut(i, deq.back().i);
            deq.back().l = c + 1;
            nw.r = c;
        }
        if (nw.r >= i+1) deq.push_back(nw);
    }
    pary(dp, dp+M+1);
    if (*min_element(dp, dp+M+1) < 0) return 0;
	else return 1;
}

Compilation message

teams.cpp: In function 'Node* ins(int, int, int*, int, Node*)':
teams.cpp:116:47: warning: conversion from 'long int' to 'int' may change value [-Wconversion]
  116 |         int ls = lower_bound(elm, elm+sz, nM) - elm;
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~

Subtask #1
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 470124 KB Output is correct
2 Correct 271 ms 470136 KB Output is correct
3 Correct 271 ms 470028 KB Output is correct
4 Correct 272 ms 470008 KB Output is correct
5 Correct 270 ms 470008 KB Output is correct
6 Correct 279 ms 470036 KB Output is correct
7 Correct 277 ms 470136 KB Output is correct
8 Correct 277 ms 469988 KB Output is correct
9 Correct 269 ms 470008 KB Output is correct
10 Correct 278 ms 470008 KB Output is correct
11 Correct 269 ms 470032 KB Output is correct
12 Correct 280 ms 470084 KB Output is correct
13 Correct 276 ms 470180 KB Output is correct
14 Correct 281 ms 470008 KB Output is correct
15 Correct 278 ms 470044 KB Output is correct
16 Correct 269 ms 470008 KB Output is correct
17 Correct 274 ms 470008 KB Output is correct
18 Correct 285 ms 470264 KB Output is correct
19 Correct 291 ms 470008 KB Output is correct
20 Correct 276 ms 470008 KB Output is correct
21 Correct 276 ms 470008 KB Output is correct
22 Correct 280 ms 470028 KB Output is correct
23 Correct 275 ms 469968 KB Output is correct
24 Correct 284 ms 469984 KB Output is correct
25 Correct 270 ms 470008 KB Output is correct
26 Correct 274 ms 470076 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 356 ms 472428 KB Output is correct
2 Correct 351 ms 472560 KB Output is correct
3 Correct 334 ms 472428 KB Output is correct
4 Correct 350 ms 473200 KB Output is correct
5 Correct 282 ms 473324 KB Output is correct
6 Correct 285 ms 473324 KB Output is correct
7 Correct 289 ms 473324 KB Output is correct
8 Correct 290 ms 473324 KB Output is correct
9 Correct 308 ms 473832 KB Output is correct
10 Correct 296 ms 473428 KB Output is correct
11 Correct 285 ms 473432 KB Output is correct
12 Correct 293 ms 473580 KB Output is correct
13 Correct 302 ms 473580 KB Output is correct
14 Correct 303 ms 473780 KB Output is correct
15 Correct 336 ms 473748 KB Output is correct
16 Correct 332 ms 473768 KB Output is correct
17 Correct 293 ms 473620 KB Output is correct
18 Correct 293 ms 473580 KB Output is correct

Subtask #3
43.0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 422 ms 472712 KB Output is correct
2 Correct 421 ms 474340 KB Output is correct
3 Correct 582 ms 477608 KB Output is correct
4 Correct 367 ms 474476 KB Output is correct
5 Correct 658 ms 473920 KB Output is correct
6 Correct 631 ms 473964 KB Output is correct
7 Correct 675 ms 473980 KB Output is correct
8 Correct 621 ms 473932 KB Output is correct
9 Correct 298 ms 473836 KB Output is correct
10 Correct 341 ms 473876 KB Output is correct
11 Correct 358 ms 474076 KB Output is correct
12 Correct 367 ms 474348 KB Output is correct
13 Correct 490 ms 474604 KB Output is correct
14 Correct 560 ms 476140 KB Output is correct
15 Correct 530 ms 474380 KB Output is correct
16 Correct 516 ms 474348 KB Output is correct
17 Correct 539 ms 474348 KB Output is correct
18 Correct 556 ms 474348 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 916 ms 483016 KB Output is correct
2 Correct 908 ms 490080 KB Output is correct
3 Correct 1345 ms 496920 KB Output is correct
4 Correct 798 ms 490392 KB Output is correct
5 Correct 1276 ms 487456 KB Output is correct
6 Correct 1211 ms 487408 KB Output is correct
7 Correct 1269 ms 487248 KB Output is correct
8 Correct 1200 ms 487552 KB Output is correct
9 Correct 472 ms 489744 KB Output is correct
10 Correct 464 ms 487780 KB Output is correct
11 Correct 460 ms 488156 KB Output is correct
12 Correct 525 ms 488852 KB Output is correct
13 Correct 1116 ms 489712 KB Output is correct
14 Correct 1318 ms 493816 KB Output is correct
15 Correct 1085 ms 490116 KB Output is correct
16 Correct 1050 ms 490108 KB Output is correct
17 Correct 936 ms 489660 KB Output is correct
18 Correct 917 ms 489700 KB Output is correct