Submission #44841

#	Time	Username	Problem	Language	Result	Execution time	Memory
44841		RayaBurong25_1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	745 ms	54144 KiB

railroad

#include "railroad.h"
#include <set>
#include <algorithm>
#include <stdio.h>
std::set<int> EP;
std::vector<int> EPc;
long long FenR[200005];
long long FenL[200005];
void upR(int p, long long v)
{
    for (; p <= EPc.size(); p += p&-p)
        FenR[p] += v;
}
void upL(int p, long long 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], 1LL);
            upR(t[i], -1LL);
        }
        else if (s[i] > t[i])
        {
            upL(t[i], 1LL);
            upL(s[i], -1LL);
        }
    }
    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]);
        }
        // printf("r %lld\n", r);
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'void upR(int, long long int)':
railroad.cpp:11: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, long long int)':
railroad.cpp:16: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:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < EPc.size() - 1; i++)
                 ~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36