oj.uz

Submission #955679

# Submission time Handle Problem Language Result Execution time Memory
955679 2024-03-31T10:16:28 Z n3rm1n Growing Trees (BOI11_grow) C++17
40 / 100
 1000 ms 4760 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 1e5 + 10;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m;
int a[MAXN];
vector < int > g;
void read_array()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        cin >> a[i];
        g.push_back(a[i]);
    }
    sort(g.begin(), g.end());
}

void upd(int c, int h)
{
    vector < int > v;
    vector < int > used;
    for (int i = 0; i < n; ++ i)
        used.push_back(0);

    int left = c, last_marked = 0;
    int first_marked = -1;
    for (int i = 0; i < g.size(); ++ i)
    {
        if(g[i] >= h && left)
        {
            left --;
            last_marked = g[i];
            used[i] = 1;
        }
        else if(g[i] >= h && !left && g[i] == last_marked)
        {
            used[i] = 2;
            if(first_marked == -1)first_marked = i;
        }
    }
    int taken = 0;
    for (int i = 0; i < g.size(); ++ i)
    {
        if(!used[i])v.push_back(g[i]);
        if(used[i] == 1 && !taken && g[i] == last_marked)
        {
            if(first_marked != -1)
            {
                int j = first_marked;
            while(j < g.size() && used[j] == 2)
            {
                v.push_back(g[j]);
                j ++;
            }
            taken = 1;
            }
        }
        if(used[i] == 1)v.push_back(g[i]+1);
    }
    g = v;
}
void solve()
{
    char type;
    int x, y;

    while(m --)
    {
        cin >> type >> x >> y;
        if(type == 'F')
        {

            upd(x, y);
        }
        else
        {
            /*cout << "jfieh" << endl;
            for (int i = 0; i < g.size(); ++ i)
                cout << g[i] << " ";
            cout << endl;*/
            int cut = std::distance(g.begin(), lower_bound(g.begin(), g.end(), x)) ;
            int add = std::distance(g.begin(), upper_bound(g.begin(), g.end(), y));
            cout << max(0, add - cut) << endl;
        }
    }
}
int main()
{
    speed();

    read_array();
    solve();
    return 0;
}
/***
5 7
1 3 2 5 2
F 2 1
C 3 6
F 2 3
C 6 8
F 2 1
F 2 2
C 3 5


*/

Compilation message

grow.cpp: In function 'void upd(int, int)':
grow.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~
grow.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for (int i = 0; i < g.size(); ++ i)
      |                     ~~^~~~~~~~~~
grow.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             while(j < g.size() && used[j] == 2)
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1056 ms 3340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 118 ms 1500 KB Output is correct
6 Correct 149 ms 1716 KB Output is correct
7 Correct 70 ms 600 KB Output is correct
8 Correct 33 ms 1248 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 237 ms 1788 KB Output is correct
2 Correct 228 ms 1784 KB Output is correct
3 Correct 14 ms 652 KB Output is correct
4 Correct 44 ms 1364 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 262 ms 2084 KB Output is correct
2 Correct 231 ms 1904 KB Output is correct
3 Correct 238 ms 708 KB Output is correct
4 Correct 174 ms 2324 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1089 ms 2380 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1004 ms 3100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1032 ms 3220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 2780 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1033 ms 3276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 731 ms 4760 KB Output is correct