oj.uz

Submission #955652

# Submission time Handle Problem Language Result Execution time Memory
955652 2024-03-31T09:04:28 Z n3rm1n Growing Trees (BOI11_grow) C++17
0 / 100
 1000 ms 3540 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;
    int i = 0;
    while (i < g.size())
    {
        if(g[i] == h)break;
        v.push_back(g[i]);
       // cout << i  << " " << g[i] << endl;
        i ++;
    }
    //cout << i << endl;
    int not_moved = i + c;
    int cut_to = i + c;
    while(not_moved < g.size() && g[not_moved] <= g[i]+1)
    {
        v.push_back(g[not_moved]);
        //cout << not_moved << endl;
        not_moved ++;
        cut_to = not_moved;
    }
    //cout << "smaller or eq " << v.size() << endl;
    for (int j = i; j < min((int)(g.size()), i + c); ++ j)
        v.push_back(g[j] + 1);
   // cout << "cut to " << cut_to << endl;
    for (int j = cut_to; j < g.size(); ++ j)
        v.push_back(g[j]);
    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 << add - cut << endl;
        }
    }
}
int main()
{
    speed();

    read_array();
    solve();
    return 0;
}

Compilation message

grow.cpp: In function 'void upd(int, int)':
grow.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     while (i < g.size())
      |            ~~^~~~~~~~~~
grow.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while(not_moved < g.size() && g[not_moved] <= g[i]+1)
      |           ~~~~~~~~~~^~~~~~~~~~
grow.cpp:50:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for (int j = cut_to; j < g.size(); ++ j)
      |                          ~~^~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 1336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 1364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 1664 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 1010 ms 2356 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 1038 ms 2472 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 1016 ms 2308 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 1026 ms 2940 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 379 ms 3540 KB Output isn't correct
2 Halted 0 ms 0 KB -