답안 #764618

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
764618	2023-06-23T16:35:27 Z	Ahmed57	Boat (APIO16_boat)	C++17	31 / 100	1277 ms	71224 KB

boat

#include <bits/stdc++.h>
using namespace std;
#define int long long
long long z = 0;
long long bit[1000001];
long long mod = 1000000007;
void add(long long e,long long v){
    while(e<=z){
        bit[e]+=v;
        bit[e]%=mod;
        e+=(e&-e);
    }
}
long long sum(long long e){
    long long res = 0;
    while(e>=1){
        res+=bit[e];
        res%=mod;
        e-=(e&-e);
    }
    return res;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    map<long long,long long> comp,sav;
    vector<pair<long long,long long>> v;
    vector<long long> ans;
    for(int i = 0;i<n;i++){
        long long x,y;
        cin>>x>>y;
        v.push_back({x,y});
        for(int i = x-250;i<=x+250;i++){
            ans.push_back(i);
        }
        for(int i = y-250;i<=y+250;i++){
            ans.push_back(i);
        }
    }
    sort(ans.begin(),ans.end());
    vector<pair<long long,long long>> all[n];
    for(int i = 0;i<v.size();i++){
        long long st = v[i].first;
        while(st<=v[i].second){
            int it = lower_bound(ans.begin(),ans.end(),st+1)-ans.begin();
            all[i].push_back({st,ans[it]-1});
            comp[st]++;comp[ans[it]-1]++;
            st = ans[it];
        }
    }
    for(auto i:comp){
        sav[i.first] = ++z;
    }
    long long fin = 0;
    for(int i = n-1;i>=0;i--){
        for(auto j:all[i]){
            long long val = (((sum(z)-sum(sav[j.second])+1)%mod)+mod)%mod;
            long long sz = (val*((j.second-j.first+1)%mod))%mod;
            fin+=sz;fin%=mod;
            add(sav[j.first],sz);
        }
    }
    cout<<fin<<endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:43:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i = 0;i<v.size();i++){
      |                   ~^~~~~~~~~

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	4544 KB	Output is correct
2	Correct	19 ms	4556 KB	Output is correct
3	Correct	18 ms	4556 KB	Output is correct
4	Correct	19 ms	4556 KB	Output is correct
5	Correct	19 ms	4556 KB	Output is correct
6	Correct	15 ms	4556 KB	Output is correct
7	Correct	17 ms	4556 KB	Output is correct
8	Correct	15 ms	4556 KB	Output is correct
9	Correct	16 ms	4556 KB	Output is correct
10	Correct	15 ms	4556 KB	Output is correct
11	Correct	15 ms	4556 KB	Output is correct
12	Correct	15 ms	4556 KB	Output is correct
13	Correct	16 ms	4556 KB	Output is correct
14	Correct	15 ms	4556 KB	Output is correct
15	Correct	16 ms	4556 KB	Output is correct
16	Correct	19 ms	4556 KB	Output is correct
17	Correct	19 ms	4556 KB	Output is correct
18	Correct	19 ms	4556 KB	Output is correct
19	Correct	19 ms	4556 KB	Output is correct
20	Correct	19 ms	4556 KB	Output is correct

Subtask #2
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	4544 KB	Output is correct
2	Correct	19 ms	4556 KB	Output is correct
3	Correct	18 ms	4556 KB	Output is correct
4	Correct	19 ms	4556 KB	Output is correct
5	Correct	19 ms	4556 KB	Output is correct
6	Correct	15 ms	4556 KB	Output is correct
7	Correct	17 ms	4556 KB	Output is correct
8	Correct	15 ms	4556 KB	Output is correct
9	Correct	16 ms	4556 KB	Output is correct
10	Correct	15 ms	4556 KB	Output is correct
11	Correct	15 ms	4556 KB	Output is correct
12	Correct	15 ms	4556 KB	Output is correct
13	Correct	16 ms	4556 KB	Output is correct
14	Correct	15 ms	4556 KB	Output is correct
15	Correct	16 ms	4556 KB	Output is correct
16	Correct	19 ms	4556 KB	Output is correct
17	Correct	19 ms	4556 KB	Output is correct
18	Correct	19 ms	4556 KB	Output is correct
19	Correct	19 ms	4556 KB	Output is correct
20	Correct	19 ms	4556 KB	Output is correct
21	Correct	273 ms	20888 KB	Output is correct
22	Correct	273 ms	20708 KB	Output is correct
23	Correct	264 ms	20000 KB	Output is correct
24	Correct	291 ms	21224 KB	Output is correct
25	Correct	292 ms	21152 KB	Output is correct
26	Correct	304 ms	20760 KB	Output is correct
27	Correct	315 ms	20784 KB	Output is correct
28	Correct	318 ms	20792 KB	Output is correct
29	Correct	329 ms	20784 KB	Output is correct
30	Correct	175 ms	38968 KB	Output is correct
31	Correct	171 ms	39016 KB	Output is correct
32	Correct	171 ms	39192 KB	Output is correct
33	Correct	169 ms	39308 KB	Output is correct
34	Correct	170 ms	38980 KB	Output is correct
35	Correct	169 ms	37976 KB	Output is correct
36	Correct	173 ms	38252 KB	Output is correct
37	Correct	173 ms	39268 KB	Output is correct
38	Correct	178 ms	38460 KB	Output is correct

Subtask #3
0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	1277 ms	71224 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	4544 KB	Output is correct
2	Correct	19 ms	4556 KB	Output is correct
3	Correct	18 ms	4556 KB	Output is correct
4	Correct	19 ms	4556 KB	Output is correct
5	Correct	19 ms	4556 KB	Output is correct
6	Correct	15 ms	4556 KB	Output is correct
7	Correct	17 ms	4556 KB	Output is correct
8	Correct	15 ms	4556 KB	Output is correct
9	Correct	16 ms	4556 KB	Output is correct
10	Correct	15 ms	4556 KB	Output is correct
11	Correct	15 ms	4556 KB	Output is correct
12	Correct	15 ms	4556 KB	Output is correct
13	Correct	16 ms	4556 KB	Output is correct
14	Correct	15 ms	4556 KB	Output is correct
15	Correct	16 ms	4556 KB	Output is correct
16	Correct	19 ms	4556 KB	Output is correct
17	Correct	19 ms	4556 KB	Output is correct
18	Correct	19 ms	4556 KB	Output is correct
19	Correct	19 ms	4556 KB	Output is correct
20	Correct	19 ms	4556 KB	Output is correct
21	Correct	273 ms	20888 KB	Output is correct
22	Correct	273 ms	20708 KB	Output is correct
23	Correct	264 ms	20000 KB	Output is correct
24	Correct	291 ms	21224 KB	Output is correct
25	Correct	292 ms	21152 KB	Output is correct
26	Correct	304 ms	20760 KB	Output is correct
27	Correct	315 ms	20784 KB	Output is correct
28	Correct	318 ms	20792 KB	Output is correct
29	Correct	329 ms	20784 KB	Output is correct
30	Correct	175 ms	38968 KB	Output is correct
31	Correct	171 ms	39016 KB	Output is correct
32	Correct	171 ms	39192 KB	Output is correct
33	Correct	169 ms	39308 KB	Output is correct
34	Correct	170 ms	38980 KB	Output is correct
35	Correct	169 ms	37976 KB	Output is correct
36	Correct	173 ms	38252 KB	Output is correct
37	Correct	173 ms	39268 KB	Output is correct
38	Correct	178 ms	38460 KB	Output is correct
39	Incorrect	1277 ms	71224 KB	Output isn't correct
40	Halted	0 ms	0 KB	-

답안 #764618

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 22.0 / 22.0

Subtask #3 0 / 27.0

Subtask #4 0 / 42.0

Subtask #1
9.0 / 9.0

Subtask #2
22.0 / 22.0

Subtask #3
0 / 27.0

Subtask #4
0 / 42.0