oj.uz

Submission #1065391

# Submission time Handle Problem Language Result Execution time Memory
1065391 2024-08-19T06:56:01 Z 정희우(#11119) Food Court (JOI21_foodcourt) C++17
68 / 100
 1000 ms 432672 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
using lint = long long;
using vint = vector<int>;
using pii = pair<int,int>;
using pli = pair<lint,int>;

const int MAX_N=250010;

struct Seg
{
    lint minus_,plus_;
    int oi;
    void addv(lint v)
    {
        if(plus_+v<0)
        {
            minus_+=plus_+v;
            plus_=0;
        }
        else
            plus_+=v;
    }
};

int n,m,q;
int idx=0;
vector<vector<pair<lint,int>>> obj;
Seg seg[MAX_N<<2];

int findo(int oi,lint v)
{
    int p=lower_bound(obj[oi].begin(),obj[oi].end(),(pli){v,-MAX_N})-obj[oi].begin();
    if(p==obj[oi].size())return 0;
    if(obj[oi][p].second<0)return obj[oi][p].second+MAX_N;
    if(p)v-=obj[oi][p-1].first;
    return findo(obj[oi][p].second,v);
}

void pushobj(int oi,lint v,int j)
{
    if(!obj[oi].empty())v+=obj[oi].back().first;
    obj[oi].push_back({v,j});
}

void update_down(const Seg &p,Seg &c)
{
    c.addv(p.minus_);
    c.addv(p.plus_);
    if(!obj[p.oi].empty())pushobj(c.oi,obj[p.oi].back().first,p.oi);
}

void update_lazy(int i)
{
    update_down(seg[i],seg[i<<1]);
    update_down(seg[i],seg[i<<1|1]);
    seg[i].minus_=seg[i].plus_=0;
    if(obj[seg[i].oi].empty())return;
    seg[i].oi=idx++;
    obj.push_back({});
}

void init_(int i,int s,int e)
{
    seg[i].minus_=seg[i].plus_=0;
    seg[i].oi=idx++;
    obj.push_back({});
    if(s+1==e)return;
    init_(i<<1,s,(s+e)>>1);
    init_(i<<1|1,(s+e)>>1,e);
}

void update_(int i,int s,int e,int l,int r,lint v,int c)
{
    if(s>=r || e<=l)return;
    if(l<=s && e<=r)
    {
        seg[i].addv(v);
        if(v>0)pushobj(seg[i].oi,v,c-MAX_N);
        return;
    }
    update_lazy(i);
    update_(i<<1,s,(s+e)>>1,l,r,v,c);
    update_(i<<1|1,(s+e)>>1,e,l,r,v,c);
}

int find_(int i,int s,int e,int x,lint v)
{
    if(s>x || e<=x)return 0;
    if(s==x && x+1==e)
    {
        v-=seg[i].plus_;
        if(!obj[seg[i].oi].empty())v+=obj[seg[i].oi].back().first;
        return findo(seg[i].oi,v);
    }
    update_lazy(i);
    return find_(i<<1,s,(s+e)>>1,x,v)+find_(i<<1|1,(s+e)>>1,e,x,v);
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m >> q;
    init_(1,0,n);
    while(q--)
    {
        int t,l,r,c;
        lint v;
        cin >> t;
        if(t==1)
        {
            cin >> l >> r >> c >> v;l--;
            update_(1,0,n,l,r,v,c);
        }
        if(t==2)
        {
            cin >> l >> r >> v;l--;
            update_(1,0,n,l,r,-v,0);
        }
        if(t==3)
        {
            cin >> l >> v;l--;
            cout << find_(1,0,n,l,v) << '\n';
        }
    }
    return 0;
}

Compilation message

foodcourt.cpp: In function 'int findo(int, lint)':
foodcourt.cpp:37:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     if(p==obj[oi].size())return 0;
      |        ~^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1428 KB Output is correct
2 Correct 5 ms 2008 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 4 ms 2268 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1636 KB Output is correct
8 Correct 5 ms 2144 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 4 ms 2144 KB Output is correct
11 Correct 5 ms 2144 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 1120 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 5 ms 1380 KB Output is correct
17 Correct 3 ms 2200 KB Output is correct
18 Correct 4 ms 2012 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 2 ms 860 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1428 KB Output is correct
2 Correct 5 ms 2008 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 4 ms 2268 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1636 KB Output is correct
8 Correct 5 ms 2144 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 4 ms 2144 KB Output is correct
11 Correct 5 ms 2144 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 1120 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 5 ms 1380 KB Output is correct
17 Correct 3 ms 2200 KB Output is correct
18 Correct 4 ms 2012 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 1908 KB Output is correct
22 Correct 4 ms 2144 KB Output is correct
23 Correct 4 ms 2200 KB Output is correct
24 Correct 4 ms 2268 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 3 ms 1632 KB Output is correct
28 Correct 6 ms 2204 KB Output is correct
29 Correct 4 ms 2144 KB Output is correct
30 Correct 4 ms 2144 KB Output is correct
31 Correct 4 ms 2144 KB Output is correct
32 Correct 4 ms 2144 KB Output is correct
33 Correct 2 ms 1096 KB Output is correct
34 Correct 2 ms 1120 KB Output is correct
35 Correct 2 ms 1432 KB Output is correct
36 Correct 3 ms 1456 KB Output is correct
37 Correct 1 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 13380 KB Output is correct
2 Correct 54 ms 15304 KB Output is correct
3 Correct 64 ms 15412 KB Output is correct
4 Correct 74 ms 15792 KB Output is correct
5 Correct 62 ms 18096 KB Output is correct
6 Correct 60 ms 17280 KB Output is correct
7 Correct 13 ms 1164 KB Output is correct
8 Correct 14 ms 2452 KB Output is correct
9 Correct 61 ms 14520 KB Output is correct
10 Correct 51 ms 15796 KB Output is correct
11 Correct 50 ms 15800 KB Output is correct
12 Correct 50 ms 14628 KB Output is correct
13 Correct 47 ms 17596 KB Output is correct
14 Correct 50 ms 16092 KB Output is correct
15 Correct 58 ms 18876 KB Output is correct
16 Correct 64 ms 18644 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 432672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1428 KB Output is correct
2 Correct 5 ms 2008 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 4 ms 2268 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1636 KB Output is correct
8 Correct 5 ms 2144 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 4 ms 2144 KB Output is correct
11 Correct 5 ms 2144 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 1120 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 5 ms 1380 KB Output is correct
17 Correct 3 ms 2200 KB Output is correct
18 Correct 4 ms 2012 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 59 ms 13380 KB Output is correct
22 Correct 54 ms 15304 KB Output is correct
23 Correct 64 ms 15412 KB Output is correct
24 Correct 74 ms 15792 KB Output is correct
25 Correct 62 ms 18096 KB Output is correct
26 Correct 60 ms 17280 KB Output is correct
27 Correct 13 ms 1164 KB Output is correct
28 Correct 14 ms 2452 KB Output is correct
29 Correct 61 ms 14520 KB Output is correct
30 Correct 51 ms 15796 KB Output is correct
31 Correct 50 ms 15800 KB Output is correct
32 Correct 50 ms 14628 KB Output is correct
33 Correct 47 ms 17596 KB Output is correct
34 Correct 50 ms 16092 KB Output is correct
35 Correct 58 ms 18876 KB Output is correct
36 Correct 64 ms 18644 KB Output is correct
37 Correct 273 ms 111524 KB Output is correct
38 Correct 237 ms 87460 KB Output is correct
39 Correct 12 ms 1504 KB Output is correct
40 Correct 13 ms 2216 KB Output is correct
41 Correct 196 ms 67944 KB Output is correct
42 Correct 285 ms 112032 KB Output is correct
43 Correct 273 ms 110756 KB Output is correct
44 Correct 282 ms 86176 KB Output is correct
45 Correct 298 ms 112472 KB Output is correct
46 Correct 287 ms 109668 KB Output is correct
47 Correct 71 ms 33452 KB Output is correct
48 Correct 171 ms 73204 KB Output is correct
49 Correct 181 ms 73588 KB Output is correct
50 Correct 258 ms 109728 KB Output is correct
51 Correct 295 ms 111516 KB Output is correct
52 Correct 322 ms 111264 KB Output is correct
53 Correct 55 ms 17328 KB Output is correct
54 Correct 68 ms 18864 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 87196 KB Output is correct
2 Correct 296 ms 114592 KB Output is correct
3 Correct 288 ms 114592 KB Output is correct
4 Correct 203 ms 73128 KB Output is correct
5 Correct 246 ms 86692 KB Output is correct
6 Correct 302 ms 114848 KB Output is correct
7 Correct 16 ms 2264 KB Output is correct
8 Correct 24 ms 3088 KB Output is correct
9 Correct 118 ms 52396 KB Output is correct
10 Correct 147 ms 60876 KB Output is correct
11 Correct 237 ms 84384 KB Output is correct
12 Correct 260 ms 84352 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1428 KB Output is correct
2 Correct 5 ms 2008 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 4 ms 2268 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1636 KB Output is correct
8 Correct 5 ms 2144 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 4 ms 2144 KB Output is correct
11 Correct 5 ms 2144 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 1120 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 5 ms 1380 KB Output is correct
17 Correct 3 ms 2200 KB Output is correct
18 Correct 4 ms 2012 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 1908 KB Output is correct
22 Correct 4 ms 2144 KB Output is correct
23 Correct 4 ms 2200 KB Output is correct
24 Correct 4 ms 2268 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 3 ms 1632 KB Output is correct
28 Correct 6 ms 2204 KB Output is correct
29 Correct 4 ms 2144 KB Output is correct
30 Correct 4 ms 2144 KB Output is correct
31 Correct 4 ms 2144 KB Output is correct
32 Correct 4 ms 2144 KB Output is correct
33 Correct 2 ms 1096 KB Output is correct
34 Correct 2 ms 1120 KB Output is correct
35 Correct 2 ms 1432 KB Output is correct
36 Correct 3 ms 1456 KB Output is correct
37 Correct 1 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 59 ms 13380 KB Output is correct
40 Correct 54 ms 15304 KB Output is correct
41 Correct 64 ms 15412 KB Output is correct
42 Correct 74 ms 15792 KB Output is correct
43 Correct 62 ms 18096 KB Output is correct
44 Correct 60 ms 17280 KB Output is correct
45 Correct 13 ms 1164 KB Output is correct
46 Correct 14 ms 2452 KB Output is correct
47 Correct 61 ms 14520 KB Output is correct
48 Correct 51 ms 15796 KB Output is correct
49 Correct 50 ms 15800 KB Output is correct
50 Correct 50 ms 14628 KB Output is correct
51 Correct 47 ms 17596 KB Output is correct
52 Correct 50 ms 16092 KB Output is correct
53 Correct 58 ms 18876 KB Output is correct
54 Correct 64 ms 18644 KB Output is correct
55 Correct 273 ms 111524 KB Output is correct
56 Correct 237 ms 87460 KB Output is correct
57 Correct 12 ms 1504 KB Output is correct
58 Correct 13 ms 2216 KB Output is correct
59 Correct 196 ms 67944 KB Output is correct
60 Correct 285 ms 112032 KB Output is correct
61 Correct 273 ms 110756 KB Output is correct
62 Correct 282 ms 86176 KB Output is correct
63 Correct 298 ms 112472 KB Output is correct
64 Correct 287 ms 109668 KB Output is correct
65 Correct 71 ms 33452 KB Output is correct
66 Correct 171 ms 73204 KB Output is correct
67 Correct 181 ms 73588 KB Output is correct
68 Correct 258 ms 109728 KB Output is correct
69 Correct 295 ms 111516 KB Output is correct
70 Correct 322 ms 111264 KB Output is correct
71 Correct 55 ms 17328 KB Output is correct
72 Correct 68 ms 18864 KB Output is correct
73 Correct 270 ms 87196 KB Output is correct
74 Correct 296 ms 114592 KB Output is correct
75 Correct 288 ms 114592 KB Output is correct
76 Correct 203 ms 73128 KB Output is correct
77 Correct 246 ms 86692 KB Output is correct
78 Correct 302 ms 114848 KB Output is correct
79 Correct 16 ms 2264 KB Output is correct
80 Correct 24 ms 3088 KB Output is correct
81 Correct 118 ms 52396 KB Output is correct
82 Correct 147 ms 60876 KB Output is correct
83 Correct 237 ms 84384 KB Output is correct
84 Correct 260 ms 84352 KB Output is correct
85 Correct 278 ms 111016 KB Output is correct
86 Correct 274 ms 109988 KB Output is correct
87 Correct 278 ms 114156 KB Output is correct
88 Correct 326 ms 112656 KB Output is correct
89 Correct 141 ms 58800 KB Output is correct
90 Correct 320 ms 112544 KB Output is correct
91 Correct 212 ms 81456 KB Output is correct
92 Correct 199 ms 78244 KB Output is correct
93 Correct 298 ms 110484 KB Output is correct
94 Correct 237 ms 86648 KB Output is correct
95 Correct 295 ms 111724 KB Output is correct
96 Correct 280 ms 110564 KB Output is correct
97 Correct 299 ms 111524 KB Output is correct
98 Correct 241 ms 85740 KB Output is correct
99 Correct 78 ms 33968 KB Output is correct
100 Correct 151 ms 63392 KB Output is correct
101 Correct 182 ms 73300 KB Output is correct
102 Correct 148 ms 57624 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1428 KB Output is correct
2 Correct 5 ms 2008 KB Output is correct
3 Correct 4 ms 2160 KB Output is correct
4 Correct 4 ms 2268 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 4 ms 1636 KB Output is correct
8 Correct 5 ms 2144 KB Output is correct
9 Correct 5 ms 2012 KB Output is correct
10 Correct 4 ms 2144 KB Output is correct
11 Correct 5 ms 2144 KB Output is correct
12 Correct 5 ms 2012 KB Output is correct
13 Correct 2 ms 1084 KB Output is correct
14 Correct 2 ms 1120 KB Output is correct
15 Correct 2 ms 1132 KB Output is correct
16 Correct 5 ms 1380 KB Output is correct
17 Correct 3 ms 2200 KB Output is correct
18 Correct 4 ms 2012 KB Output is correct
19 Correct 1 ms 856 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 3 ms 1908 KB Output is correct
22 Correct 4 ms 2144 KB Output is correct
23 Correct 4 ms 2200 KB Output is correct
24 Correct 4 ms 2268 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 3 ms 1632 KB Output is correct
28 Correct 6 ms 2204 KB Output is correct
29 Correct 4 ms 2144 KB Output is correct
30 Correct 4 ms 2144 KB Output is correct
31 Correct 4 ms 2144 KB Output is correct
32 Correct 4 ms 2144 KB Output is correct
33 Correct 2 ms 1096 KB Output is correct
34 Correct 2 ms 1120 KB Output is correct
35 Correct 2 ms 1432 KB Output is correct
36 Correct 3 ms 1456 KB Output is correct
37 Correct 1 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 59 ms 13380 KB Output is correct
40 Correct 54 ms 15304 KB Output is correct
41 Correct 64 ms 15412 KB Output is correct
42 Correct 74 ms 15792 KB Output is correct
43 Correct 62 ms 18096 KB Output is correct
44 Correct 60 ms 17280 KB Output is correct
45 Correct 13 ms 1164 KB Output is correct
46 Correct 14 ms 2452 KB Output is correct
47 Correct 61 ms 14520 KB Output is correct
48 Correct 51 ms 15796 KB Output is correct
49 Correct 50 ms 15800 KB Output is correct
50 Correct 50 ms 14628 KB Output is correct
51 Correct 47 ms 17596 KB Output is correct
52 Correct 50 ms 16092 KB Output is correct
53 Correct 58 ms 18876 KB Output is correct
54 Correct 64 ms 18644 KB Output is correct
55 Execution timed out 1071 ms 432672 KB Time limit exceeded
56 Halted 0 ms 0 KB -