oj.uz

Submission #893384

# Submission time Handle Problem Language Result Execution time Memory
893384 2023-12-27T03:56:16 Z 1075508020060209tc A Game with Grundy (CCO20_day1problem1) C++14
25 / 25
 84 ms 8124 KB 
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
//#define Y second
vector<pair<int,int>>event;
int n;int L;int R;int Y;

int ans[500005];
void init(){
cin>>n;
cin>>L>>R>>Y;

for(int i=1;i<=n;i++){
    int a;int p;int q;
    cin>>a>>p>>q;
    int r=(Y+p*a/q)*q/p;
    r=Y*q/p+a;
    int l=(Y-p*a/q)*(-q)/p;
    l=Y*(-q)/p+a;
    if((Y*q)%p==0){r--;l++;}
    l=max(l,L);
    r=min(r,R);
    if(r>=l){
        event.push_back({l,1});
        event.push_back({r+1,-1});
    }
}
event.push_back({L,0});
event.push_back({R+1,0});
sort(event.begin(),event.end());
int tot=0;
//cout<<endl;
for(int i=0;i<event.size()-1;i++){
    tot+=event[i].second;
    ans[tot]+=event[i+1].first-event[i].first;

   // cout<<event[i].first<<" "<<event[i].second<<"\n";

}
for(int i=1;i<=n;i++){
    ans[i]+=ans[i-1];
}
for(int i=0;i<=n;i++){
    cout<<ans[i]<<"\n";
}



}


signed main(){
init();

}

Compilation message

Main.cpp: In function 'void init()':
Main.cpp:35:14: 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]
   35 | for(int i=0;i<event.size()-1;i++){
      |             ~^~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 69 ms 5580 KB Output is correct
4 Correct 73 ms 6448 KB Output is correct
5 Correct 74 ms 6852 KB Output is correct
6 Correct 60 ms 7352 KB Output is correct
7 Correct 54 ms 8120 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 69 ms 5580 KB Output is correct
4 Correct 73 ms 6448 KB Output is correct
5 Correct 74 ms 6852 KB Output is correct
6 Correct 60 ms 7352 KB Output is correct
7 Correct 54 ms 8120 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 77 ms 7804 KB Output is correct
10 Correct 84 ms 6960 KB Output is correct
11 Correct 80 ms 7608 KB Output is correct
12 Correct 79 ms 6920 KB Output is correct
13 Correct 55 ms 8124 KB Output is correct