Submission #563258

#	Time	Username	Problem	Language	Result	Execution time	Memory
563258		Tien_Noob	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	162 ms	122940 KiB

street_lamps

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 3e5;
set<pair<int, int> > pivot, dp[N + 1];
set<int> query[N + 1];
map<int, int> res[N + 1];
int n, q, t[N + 1], a[N + 1], b[N + 1];
string s;
set<pair<int, int> > :: iterator Range(int x)
{
    auto it = pivot.upper_bound({x, N + 1});
    --it;
    return it;
}
void read()
{
    cin >> n >> q >> s;
    s = '?' + s;
    for (int i = 1; i <= q; ++ i)
    {
        string r;
        cin >> r;
        if (r == "query")
        {
            t[i] = 1;
            cin >> a[i] >> b[i];
            query[a[i]].insert(b[i]);
        }
        else
        {
            t[i] = 0;
            cin >> a[i];
        }
    }
    for (int i = 1; i <= n + 1; ++ i)
    {
        pivot.insert({i, i});
        if (!query[i].empty())
        {
            dp[i].insert({*query[i].begin(), i});
        }
    }
    for (int i = 1; i <= n; ++ i)
    {
        if (s[i] == '1')
        {
            pair<int, int> tmp =  *Range(i);
            pivot.erase(tmp);
            pivot.erase({i + 1, i + 1});
            pivot.insert({tmp.first, i + 1});
            swap(dp[i], dp[i + 1]);
            for (auto &p : dp[i])
            {
                dp[i + 1].insert(p);
            }
            dp[i].clear();
        }
    }
    for (int i = 1; i <= n + 1; ++ i)
    {
        while(!dp[i].empty() && dp[i].begin()->first <= i)
        {
            int u = dp[i].begin()->second;
            res[u][dp[i].begin()->first] = 0;
            query[u].erase(query[u].begin());
            dp[i].erase(dp[i].begin());
            if (!query[u].empty())
            {
                dp[i].insert({*query[u].begin(), u});
            }
        }
    }
}
void solve()
{
    for (int i = 1; i <= q; ++ i)
    {
        if (t[i] == 0)
        {
            if (s[a[i]] == '1')
            {
                auto it = Range(a[i]);
                int l = it->first, r = it->second;
                pivot.erase(it);
                pivot.insert({l, a[i]});
                pivot.insert({a[i] + 1, r});
                s[a[i]] = '0';
            }
            else
            {
                auto it1 = Range(a[i]), it2 = Range(a[i] + 1);
                int l = it1->first, r = it2->second;
                if (dp[a[i]].size() > dp[r].size())
                {
                    swap(dp[a[i]], dp[r]);
                }
                for (auto &p : dp[a[i]])
                {
                    dp[r].insert(p);
                }
                dp[a[i]].clear();
                while(!dp[r].empty() && dp[r].begin()->first <= r)
                {
                    int u = dp[r].begin()->second;
                    res[u][dp[r].begin()->first] = i;
                    query[u].erase(query[u].begin());
                    dp[r].erase(dp[r].begin());
                    if (!query[u].empty())
                    {
                        dp[r].insert({*query[u].begin(), u});
                    }
                }
                pivot.erase(it1);
                pivot.erase(it2);
                pivot.insert({l, r});
                s[a[i]] = '1';
            }
        }
        else
        {
            if (res[a[i]].find(b[i]) == res[a[i]].end())
            {
                cout << 0 << '\n';
            }
            else
            {
                cout << i - res[a[i]][b[i]] << '\n';
            }
        }
    }
}
int  main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        //freopen(TASK".OUT", "w", stdout);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  142 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20