oj.uz

Submission #763681

# Submission time Handle Problem Language Result Execution time Memory
763681 2023-06-22T15:31:29 Z HoriaHaivas Pilot (NOI19_pilot) C++14
0 / 100
 37 ms 5056 KB 
/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

struct number
{
    int val;
    int poz;
};

number v[2000001];
bool enable[2000001];
int ans[2000001];
int query[2000001];
int originalquery[2000001];
int cardinal[2000001];
int root[2000001];
int total;

bool cmp (number a, number b)
{
    if (a.val!=b.val)
    return a.val<b.val;
    else
    return a.poz<b.poz;
}

void unite(int a, int b)
{
    if (cardinal[a]>cardinal[b])
        swap(a,b);
    root[a]=root[b];
    cardinal[b]+=cardinal[a];
    cardinal[a]=cardinal[b];
}

int searchset(int a)
{
    if (root[a]==a)
        return a;
    root[a]=searchset(root[a]);
    return root[a];
}

void update(int index)
{
    enable[index]=1;
    root[index]=index;
    cardinal[index]=1;
    int enter;
    enter=0;
    if (enable[index-1])
    {
        enter++;
    }
    if (enable[index+1])
    {
        enter++;
    }
    if (enter==0)
        total++;
    if (enter==1)
    {
        if (enable[index-1])
        {
            total+=cardinal[searchset(index-1)]+1;
            unite(searchset(index-1),searchset(index));
        }
        else
        {
            total+=cardinal[searchset(index+1)]+1;
            unite(searchset(index+1),searchset(index));
        }
    }
    if (enter==2)
    {
        total-=cardinal[searchset(index-1)]*(cardinal[searchset(index-1)]+1)/2;
        total-=cardinal[searchset(index+1)]*(cardinal[searchset(index+1)]+1)/2;
        unite(searchset(index-1),searchset(index));
        unite(searchset(index+1),searchset(index));
        total+=cardinal[searchset(index)]*(cardinal[searchset(index)]+1)/2;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,q,i,j,cnt;
    cin >> n >> q;
    for (i=1; i<=n; i++)
    {
        cin >> v[i].val;
        v[i].poz=i;
    }
    for (i=1;i<=q;i++)
    {
         cin >> originalquery[i];
         query[i]=originalquery[i];
    }
    sort(query+1,query+1+q);
    sort(v+1,v+1+n,cmp);
    cnt=1;
    total=0;
    for (i=1; i<=n; i++)
    {
        update(v[i].poz);
        if (v[i].val!=v[i+1].val && query[cnt]==v[i].val)
        {
            ans[query[cnt]]=total;
            cnt++;
        }
    }
    for (i=1;i<=q;i++)
    {
         cout << ans[originalquery[i]] << "\n";
    }
}

Compilation message

pilot.cpp: In function 'int main()':
pilot.cpp:98:15: warning: unused variable 'j' [-Wunused-variable]
   98 |     int n,q,i,j,cnt;
      |               ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 14.0

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

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -