제출 #955679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
955679		n3rm1n	Growing Trees (BOI11_grow)	C++17	40 / 100	1089 ms	4760 KiB

grow

#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


*/

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10