oj.uz

Submission #44842

# Submission time Handle Problem Language Result Execution time Memory
44842 2018-04-08T05:00:56 Z RayaBurong25_1 Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 698 ms 55552 KB 
#include "railroad.h"
#include <set>
#include <algorithm>
#include <stdio.h>
std::set<int> EP;
std::vector<int> EPc;
long long FenR[400005];
long long FenL[400005];
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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 2 ms 416 KB n = 2
4 Correct 2 ms 568 KB n = 2
5 Correct 2 ms 568 KB n = 2
6 Correct 2 ms 568 KB n = 2
7 Correct 2 ms 568 KB n = 3
8 Correct 2 ms 568 KB n = 3
9 Correct 2 ms 576 KB n = 3
10 Correct 2 ms 576 KB n = 8
11 Incorrect 2 ms 576 KB answer is not correct: 187084041 instead of 189002015
12 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 2 ms 416 KB n = 2
4 Correct 2 ms 568 KB n = 2
5 Correct 2 ms 568 KB n = 2
6 Correct 2 ms 568 KB n = 2
7 Correct 2 ms 568 KB n = 3
8 Correct 2 ms 568 KB n = 3
9 Correct 2 ms 576 KB n = 3
10 Correct 2 ms 576 KB n = 8
11 Incorrect 2 ms 576 KB answer is not correct: 187084041 instead of 189002015
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 27236 KB n = 199999
2 Correct 693 ms 34388 KB n = 199991
3 Correct 652 ms 35128 KB n = 199993
4 Correct 479 ms 35128 KB n = 152076
5 Correct 304 ms 35128 KB n = 93249
6 Correct 698 ms 40780 KB n = 199910
7 Correct 587 ms 48096 KB n = 199999
8 Correct 520 ms 48096 KB n = 199997
9 Correct 549 ms 50436 KB n = 171294
10 Correct 420 ms 50436 KB n = 140872
11 Incorrect 655 ms 55552 KB answer is not correct: 0 instead of 1
12 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB n = 2
2 Correct 2 ms 376 KB n = 2
3 Correct 2 ms 416 KB n = 2
4 Correct 2 ms 568 KB n = 2
5 Correct 2 ms 568 KB n = 2
6 Correct 2 ms 568 KB n = 2
7 Correct 2 ms 568 KB n = 3
8 Correct 2 ms 568 KB n = 3
9 Correct 2 ms 576 KB n = 3
10 Correct 2 ms 576 KB n = 8
11 Incorrect 2 ms 576 KB answer is not correct: 187084041 instead of 189002015
12 Halted 0 ms 0 KB -