oj.uz

Submission #44840

# Submission time Handle Problem Language Result Execution time Memory
44840 2018-04-08T04:46:03 Z RayaBurong25_1 Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 713 ms 54684 KB 
#include "railroad.h"
#include <set>
#include <algorithm>
std::set<int> EP;
std::vector<int> EPc;
int FenR[200005];
int FenL[200005];
void upR(int p, int v)
{
    for (; p <= EPc.size(); p += p&-p)
        FenR[p] += v;
}
void upL(int p, int v)
{
    for (; p <= EPc.size(); p += p&-p)
        FenL[p] += v;
}
long long queryR(int p)
{
    long long r = 0;
    for (; p > 0; p -= p&-p)
        r += FenR[p];
    return r;
}
long long queryL(int p)
{
    long long r = 0;
    for (; p > 0; p -= p&-p)
        r += FenL[p];
    return r;
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();
    int i;
    for (i = 0; i < n; i++)
    {
        EP.insert(s[i]);
        EP.insert(t[i]);
    }
    std::set<int>::iterator it;
    for (it = EP.begin(); it != EP.end(); it++)
        EPc.push_back(*it);
    for (i = 0; i < n; i++)
    {
        s[i] = std::lower_bound(EPc.begin(), EPc.end(), s[i]) - EPc.begin() + 1;
        t[i] = std::lower_bound(EPc.begin(), EPc.end(), t[i]) - EPc.begin() + 1;
        if (s[i] < t[i])
        {
            upR(s[i], 1);
            upR(t[i], -1);
        }
        else if (s[i] > t[i])
        {
            upL(s[i], 1);
            upL(t[i], -1);
        }
    }
    long long ans = 0, r;
    for (i = 0; i < EPc.size() - 1; i++)
    {
        if ((r = queryR(i + 1) - queryL(i + 1)) > 1)
        {
            ans += (r - 1)*(EPc[i + 1] - EPc[i]);
        }
    }
    return ans;
}

Compilation message

railroad.cpp: In function 'void upR(int, int)':
railroad.cpp:10:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; p <= EPc.size(); p += p&-p)
            ~~^~~~~~~~~~~~~
railroad.cpp: In function 'void upL(int, int)':
railroad.cpp:15:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (; p <= EPc.size(); p += p&-p)
            ~~^~~~~~~~~~~~~
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < EPc.size() - 1; i++)
                 ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB answer is not correct: 15509384 instead of 0
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB answer is not correct: 15509384 instead of 0
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 713 ms 54684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB answer is not correct: 15509384 instead of 0
2 Halted 0 ms 0 KB -