oj.uz

Submission #276731

# Submission time Handle Problem Language Result Execution time Memory
276731 2020-08-20T15:42:37 Z stoyan_malinin Teams (IOI15_teams) C++14
100 / 100
 1690 ms 379644 KB 
#include "teams.h"
//#include "grader.cpp"

#include <set>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

const int MAXN = 5e5 + 5;

struct SegmentTree
{
    int val;
    SegmentTree *L, *R;

    SegmentTree()
    {
        this->val = 0;

        this->L = nullptr;
        this->R = nullptr;
    }

    void copyFrom(SegmentTree *other)
    {
        val = other->val;
    }

    void build(int l, int r)
    {
        if(l==r) return;

        L = new SegmentTree();
        R = new SegmentTree();

        L->build(l, (l+r)/2);
        R->build((l+r)/2+1, r);
    }

    int query(int ql, int qr, int l, int r)
    {
        if(l>=ql && r<=qr) return val;
        if(r<ql || l>qr) return 0;

        return L->query(ql, qr, l, (l+r)/2) + R->query(ql, qr, (l+r)/2+1, r);
    }

    void update(int q, int change, SegmentTree *other, int l, int r)
    {
        copyFrom(other);
        //cout << l << " " << r << " -> " << q << '\n';

        if(l==r && l==q)
        {
            val += change;
            return;
        }

        if(l<=q && q<=(l+r)/2)
        {
            L = new SegmentTree();
            L->update(q, change, other->L, l, (l+r)/2);
        }
        else
        {
            L = other->L;
        }

        if((l+r)/2+1<=q && q<=r)
        {
            R = new SegmentTree();
            R->update(q, change, other->R, (l+r)/2+1, r);
        }
        else
        {
            R = other->R;
        }

        val = L->val + R->val;
    }
};

struct Event
{
    int type;
    int pos;

    pair <int, int> info;

    Event(){}
    Event(int type, int pos,  pair <int, int> info)
    {
        this->type = type;
        this->pos = pos;

        this->info = info;
    }
};

bool operator <(Event A, Event B)
{
    if(A.pos!=B.pos) return A.pos<B.pos;
    return A.type<B.type;
}

int n;
int *a, *b;

long long dp[MAXN];
SegmentTree *T[MAXN];
vector <int> start2End[MAXN];

SegmentTree* createTree()
{
    return new SegmentTree();
}

int getInside(int x1, int x2, int y1, int y2)
{
    if(x1>x2 || y1>y2) return 0;

    int ans = T[x2]->query(y1, y2, 1, n);
    if(x1!=0) ans -= T[x1-1]->query(y1, y2, 1, n);

    return ans;
}

void init(int N, int A[], int B[])
{
    n = N;
    a = A;
    b = B;

    for(int i = 0;i<n;i++)
        start2End[ a[i] ].push_back(b[i]);

    T[0] = createTree();
    T[0]->build(1, n);

    for(int i = 1;i<=n;i++)
    {
        T[i] = T[i-1];
        for(int x: start2End[i])
        {
            SegmentTree *buff = createTree();
            buff->update(x, +1, T[i], 1, n);

            T[i] = buff;
        }
    }

    /*
    while(true)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> x2 >> y1 >> y2;

        cout << getInside(x1, x2, y1, y2) << '\n';
    }
    */
}

int slowSolve(int M, int K[])
{
    multiset <pair <int, int>> s;
    vector <Event> v;

    for(int i = 0;i<n;i++)
    {
        v.push_back(Event(0, a[i], {b[i], a[i]}));
        v.push_back(Event(2, b[i], {b[i], a[i]}));
    }
    for(int i = 0;i<M;i++)
    {
        v.push_back(Event(1, K[i], {K[i], K[i]}));
    }

    sort(v.begin(), v.end());
    //for(Event e: v) cout << e.type << " -> " << e.info.first << " " << e.info.second << '\n';

    for(Event e: v)
    {
        if(e.type==0)
        {
            s.insert(e.info);
        }
        else if(e.type==1)
        {
            if(s.size()<e.info.first) return 0;
            for(int rem = 0;rem<e.info.first;rem++) s.erase(s.find(*s.begin()));
        }
        else if(e.type==2)
        {
            if(s.find(e.info)!=s.end()) s.erase(s.find(e.info));
        }

        //cout << e.type << " -> " << e.info.first << " " << e.info.second << " || " << s.size() << '\n';
    }

    return 1;
}

long long eval(int i, int j, int K[])
{
    return dp[j] + getInside(K[j]+1, K[i], K[i], n) - K[i];
}

bool quickCheck(int M, int K[])
{
    int sum = 0;
    for(int i = 0;i<M;i++)
    {
        sum += K[i];
        if(sum>n) return true;
    }

    return false;
}

int can(int M, int K[])
{
    //if(M>sqrt(n)) return slowSolve(M, K);
    if(quickCheck(M, K)==true) return 0;

    sort(K, K+M);
    for(int i = 0;i<=M;i++) dp[i] = 0;

    vector <int> inds;

    for(int i = 0;i<M;i++)
    {
        dp[i] = getInside(1, K[i], K[i], n) - K[i];
        while(inds.size()>=2 && eval(i, inds[inds.size()-2], K)<=eval(i, inds[inds.size()-1], K)) inds.pop_back();

        for(int j = inds.size()-1;j>=max(0, int(inds.size())-5);j--)
            dp[i] = min(dp[i], eval(i, inds[j], K));

        inds.push_back(i);
    }

    long long minVal = MAXN;
    for(int i = 0;i<M;i++) minVal = min(minVal, dp[i]);

    if(minVal<0) return 0;
    return 1;
}
/*
4
1 2
2 3
2 3
2 4
2
2
1 3
2
1 1
*/

Compilation message

teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:95:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:95:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:95:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
   95 |     {
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:100:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:100:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:100:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In constructor 'Event::Event(int, int, std::pair<int, int>)':
teams.cpp:100:5: warning: declaration of 'info' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:91:21: note: shadowed declaration is here
   91 |     pair <int, int> info;
      |                     ^~~~
teams.cpp:100:5: warning: declaration of 'pos' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:89:9: note: shadowed declaration is here
   89 |     int pos;
      |         ^~~
teams.cpp:100:5: warning: declaration of 'type' shadows a member of 'Event' [-Wshadow]
  100 |     }
      |     ^
teams.cpp:88:9: note: shadowed declaration is here
   88 |     int type;
      |         ^~~~
teams.cpp: In function 'int slowSolve(int, int*)':
teams.cpp:192:24: warning: comparison of integer expressions of different signedness: 'std::multiset<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  192 |             if(s.size()<e.info.first) return 0;
      |                ~~~~~~~~^~~~~~~~~~~~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:238:32: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  238 |         for(int j = inds.size()-1;j>=max(0, int(inds.size())-5);j--)
      |                     ~~~~~~~~~~~^~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12032 KB Output is correct
2 Correct 8 ms 12032 KB Output is correct
3 Correct 10 ms 12160 KB Output is correct
4 Correct 12 ms 12160 KB Output is correct
5 Correct 9 ms 12160 KB Output is correct
6 Correct 11 ms 12160 KB Output is correct
7 Correct 9 ms 12124 KB Output is correct
8 Correct 9 ms 12160 KB Output is correct
9 Correct 11 ms 12160 KB Output is correct
10 Correct 9 ms 12160 KB Output is correct
11 Correct 9 ms 12032 KB Output is correct
12 Correct 12 ms 12160 KB Output is correct
13 Correct 10 ms 12160 KB Output is correct
14 Correct 9 ms 12160 KB Output is correct
15 Correct 9 ms 12160 KB Output is correct
16 Correct 10 ms 12160 KB Output is correct
17 Correct 11 ms 12032 KB Output is correct
18 Correct 9 ms 12032 KB Output is correct
19 Correct 9 ms 12032 KB Output is correct
20 Correct 9 ms 12032 KB Output is correct
21 Correct 11 ms 12032 KB Output is correct
22 Correct 9 ms 12032 KB Output is correct
23 Correct 9 ms 12032 KB Output is correct
24 Correct 9 ms 12032 KB Output is correct
25 Correct 10 ms 12064 KB Output is correct
26 Correct 9 ms 12032 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 77428 KB Output is correct
2 Correct 173 ms 77304 KB Output is correct
3 Correct 169 ms 77432 KB Output is correct
4 Correct 174 ms 79224 KB Output is correct
5 Correct 118 ms 76024 KB Output is correct
6 Correct 117 ms 76072 KB Output is correct
7 Correct 122 ms 76104 KB Output is correct
8 Correct 114 ms 76024 KB Output is correct
9 Correct 121 ms 74472 KB Output is correct
10 Correct 109 ms 74096 KB Output is correct
11 Correct 115 ms 76784 KB Output is correct
12 Correct 109 ms 73712 KB Output is correct
13 Correct 124 ms 76932 KB Output is correct
14 Correct 159 ms 74992 KB Output is correct
15 Correct 158 ms 77048 KB Output is correct
16 Correct 161 ms 77100 KB Output is correct
17 Correct 115 ms 76920 KB Output is correct
18 Correct 126 ms 76792 KB Output is correct

Subtask #3
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 394 ms 77816 KB Output is correct
2 Correct 385 ms 77688 KB Output is correct
3 Correct 359 ms 80712 KB Output is correct
4 Correct 209 ms 79096 KB Output is correct
5 Correct 232 ms 76408 KB Output is correct
6 Correct 234 ms 76280 KB Output is correct
7 Correct 286 ms 76380 KB Output is correct
8 Correct 276 ms 76292 KB Output is correct
9 Correct 114 ms 74352 KB Output is correct
10 Correct 135 ms 74352 KB Output is correct
11 Correct 170 ms 77168 KB Output is correct
12 Correct 308 ms 74140 KB Output is correct
13 Correct 406 ms 77428 KB Output is correct
14 Correct 384 ms 78712 KB Output is correct
15 Correct 357 ms 77432 KB Output is correct
16 Correct 348 ms 77560 KB Output is correct
17 Correct 334 ms 77176 KB Output is correct
18 Correct 294 ms 77172 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1653 ms 373460 KB Output is correct
2 Correct 1679 ms 373648 KB Output is correct
3 Correct 1546 ms 379644 KB Output is correct
4 Correct 1129 ms 376432 KB Output is correct
5 Correct 830 ms 367208 KB Output is correct
6 Correct 857 ms 367224 KB Output is correct
7 Correct 1006 ms 367308 KB Output is correct
8 Correct 969 ms 367352 KB Output is correct
9 Correct 618 ms 354412 KB Output is correct
10 Correct 643 ms 367568 KB Output is correct
11 Correct 860 ms 367500 KB Output is correct
12 Correct 1072 ms 367512 KB Output is correct
13 Correct 1459 ms 368704 KB Output is correct
14 Correct 1690 ms 373592 KB Output is correct
15 Correct 1342 ms 372356 KB Output is correct
16 Correct 1342 ms 372456 KB Output is correct
17 Correct 1012 ms 374280 KB Output is correct
18 Correct 971 ms 374280 KB Output is correct