Submission #1258615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258615		phtung	Pilot (NOI19_pilot)	C++20	100 / 100	436 ms	70668 KiB

pilot

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int inf = 1e18 + 7; 
const int maxn = 1e6 + 5;
int n;

int Pow(int x, int y) 
{
    int ans = 1;
    while (y > 0) 
    {
        if (y & 1) ans = ans * x;
        y /= 2;
        x = x * x;
    }
    return ans;
}

struct DSU
{
    vector<int> par, sz;

    DSU(int n)
    {
        par.resize(n + 5); 
        sz.resize(n + 5, 1); 
        iota(par.begin(), par.end(), 0); 
    }

    int find(int x)
    {
        if(x != par[x]) par[x] = find(par[x]); 
        return par[x]; 
    }

    void join(int u, int v)
    {
        u = find(u);
        v = find(v);
        if(u == v) return;

        if(sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v]; 
    }

    int Size(int u)
    {
        int len = sz[find(u)]; 
        return len * (len + 1) / 2ll; 
    }
};

void solve()
{
    int n, q;
    cin >> n >> q; 

    vector<int> a(n + 1, 0), id(n + 1); 
    for(int i = 1; i <= n; i++) cin >> a[i]; 

    vector<pair<int,int>> query(q);
    for(int i = 0; i < q; i++)
    {
        int x; cin >> x; 
        query[i] = {x, i}; 
    }

    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&](int &x, int &y){
        return a[x] < a[y]; 
    }); 

    DSU dsu(n);
    sort(query.begin(), query.end()); 

    int ptr = 1; 
    int total = 0; 
    int ans[q]; 
    int check[n + 1]; 
    fill(check + 1, check + n + 1, 0); 

    for(auto [val, idx] : query)
    {
        while(ptr <= n && a[id[ptr]] <= val)
        {
            int pos = id[ptr]; 
            
            total += dsu.Size(pos); 

            if(pos > 1)
            {
                if(check[pos - 1])
                {
                    total -= dsu.Size(pos - 1);
                    total -= dsu.Size(pos); 
                    dsu.join(pos - 1, pos); 
                    total += dsu.Size(pos); 
                }
            }
            if(pos < n)
            {
                if(check[pos + 1])
                {
                    total -= dsu.Size(pos);
                    total -= dsu.Size(pos + 1);
                    dsu.join(pos, pos + 1);
                    total += dsu.Size(pos); 
                }
            }
            check[pos] = 1; 
            ptr++; 
        }

        ans[idx] = total; 
    }

    for(int i = 0; i < q; i++) cout << ans[i] << "\n"; 

}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:131:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pilot.cpp:132:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11