oj.uz

Submission #643346

# Submission time Handle Problem Language Result Execution time Memory
643346 2022-09-21T19:10:57 Z tigar Arranging Shoes (IOI19_shoes) C++14
10 / 100
 1 ms 212 KB 
#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll fenvick[200020];


void fenvick_add(int x, int n, int val)
{
    int x1=x;
    while(x1<=n)
    {
        fenvick[x1]+=val;
        x1+=((-x1)&x1);
    }
}

ll fenvick_sum(int x)
{
    int x1=x, rz=0;
    while(x1>0)
    {
        rz+=fenvick[x1];
        x1-=((-x1)&x1);
    }
    return rz;
}

ll count_swaps(vector<int>S)
{
    int n=S.size()/2;
    stack<int>leve[n+1], desne[n+1];
    ll reez=0;
    int poooz[n*2+1]={0};
    for(int i=0; i<2*n; i++)
    {
        if(S[i]<0)leve[-S[i]].push(i+1);
        else desne[S[i]].push(i+1);
    }

    for(int i=1; i<=n; i++)
    {
        while(!leve[i].empty())
        {
            if(desne[i].top()<leve[i].top())reez++;
            poooz[leve[i].top()]=desne[i].top();
            poooz[desne[i].top()]=leve[i].top();
            desne[i].pop();
            leve[i].pop();
        }
    }
    bool check[2*n+1]={false};
    for(int i=1; i<=2*n; i++)
    {
        if(!check[i])
        {
            fenvick_add(i, 2*n, 1);
            fenvick_add(poooz[i], 2*n, 1);
            check[i]=true;
            check[poooz[i]]=true;
        }
        else if(check[i])
        {
            fenvick_add(i, 2*n, -1);
            fenvick_add(poooz[i], 2*n, -1);
            reez+=fenvick_sum(i)-fenvick_sum(poooz[i]-1);
            fenvick_add(i, 2*n, 1);
            fenvick_add(poooz[i], 2*n, 1);
        }
    }
    return reez;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 20.0

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

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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

Subtask #6
0 / 15.0

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