Submission #1365270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1365270		minhpnk	Meteors (POI11_met)	C++20	0 / 100	488 ms	22028 KiB

met

#include <bits/stdc++.h>
#define int long long
#define taskname "main"
#define debug(a, l, r) for (int _i = (l); _i <= (r); _i++) cout<<(a)[_i]<<' '; cout<<'\n';
using namespace std;
const int maxN = 3e5;
int c_team, c_land, q, // cnt_team, cnt_lan
    goal[maxN + 1],
    t_lo[maxN + 1],
    t_hi[maxN + 1];
vector <int> list_l[maxN + 1]; // danh sach dat ma mot nguoi nam giu
struct FenTree
{
    int bit[maxN + 1];
private:
    void upd(int u, int x)
    {
        for (int i = u; i <= maxN; i += i & -i)
            bit[i] += x;
    }
public:
    void clear()
    {
        memset(bit, 0, sizeof(bit));
    }
    int get(int u)
    {
        int res = 0;
        for (int i = u; i > 0; i -= i & -i)
            res += bit[i];
        return res;
    }
    void upd_r(int l, int r, int x)
    {
        if (l > r)
        {
            upd_r(l, c_land, x);
            upd_r(1, r, x);
        }
        else
        {
            upd(l, x);
            upd(r + 1, -x);
        }
    }
} ft; //---------//
struct Update
{
    int l, r, x;
    void read()
    {
        cin >> l >> r >> x;
    }
} list_upd[maxN + 1];
struct HasI
{
    int x, i;
    bool operator < (const HasI &other) const
    {
        return x < other.x;
    }
}; vector <HasI> tmp_x; //---------//
void init()
{
    cin >> c_team >> c_land;
    for (int i = 1; i <= c_land; i++)
    {
        int boss;
        cin >> boss;
        list_l[boss].push_back(i);
    }
    for (int i = 1; i <= c_team; i++)
        cin >> goal[i];
    cin >> q;
    for (int i = 1; i <= q; i++)
        list_upd[i].read();
    for (int i = 1; i <= c_team; i++)
    {
        t_lo[i] = 1;
        t_hi[i] = q + 1;
    }
}
bool chat_all()
{
    for (int i = 1; i <= c_team; i++)
    {
        if (t_lo[i] == t_hi[i])
            continue;
        int mid = (t_lo[i] + t_hi[i]) >> 1;
        tmp_x.push_back({mid, i});
    }
    return tmp_x.size();
}
void xet_qall()
{
    int t = 1;
    for (HasI u: tmp_x)
    {
        while (t <= q && t <= u.x)
        {
            ft.upd_r(list_upd[t].l, list_upd[t].r, list_upd[t].x);
            t++;
        }
        int gold = 0;
        for (int land: list_l[u.i])
            gold += ft.get(land);
        if (gold >= goal[u.i]) // thu giam xuong
            t_hi[u.i] = u.x;
        else t_lo[u.i] = u.x + 1;
    }
}
void solve()
{
    while (chat_all())
    {
        xet_qall();
        tmp_x.clear();
        ft.clear();
    }
    for (int i = 1; i <= c_team; i++)
    {
        if (t_lo[i] == q + 1)
            cout << "NIE\n";
        else cout << t_lo[i] << '\n';
    }
}
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    if (fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    init(); solve();
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
met.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13