oj.uz

Submission #535079

# Submission time Handle Problem Language Result Execution time Memory
535079 2022-03-09T11:25:58 Z Carmel_Ab1 Examination (JOI19_examination) C++17
2 / 100
 2915 ms 1048580 KB 
/*
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 */
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//using namespace __gnu_pbds;
using namespace std;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int>vi;
typedef vector<vector<int>>vvi;
typedef vector<ll>vl;
typedef vector<vl> vvl;
typedef pair<int,int>pi;
typedef pair<ll,ll> pl;
typedef vector<pl> vpl;
typedef vector<ld> vld;
typedef pair<ld,ld> pld;
typedef vector<pi> vpi;

//typedef tree<ll, null_type, less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<typename T> ostream& operator<<(ostream& os, vector<T>& a){os<<"[";for(int i=0; i<ll(a.size()); i++){os << a[i] << ((i!=ll(a.size()-1)?" ":""));}os << "]\n"; return os;}

#define all(x) x.begin(),x.end()
#define YES out("YES")
#define NO out("NO")
#define out(x){cout << x << "\n"; return;}
#define outfl(x){cout << x << endl;return;}
#define GLHF ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define print(x){for(auto ait:x) cout << ait << " "; cout << "\n";}
#define pb push_back
#define umap unordered_map

template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1, T2>& p){is >> p.first >> p.second;return is;}
template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1, T2>& p){os <<"" << p.first << " " << p.second << ""; return os;}
void usaco(string taskname){
    string fin = taskname + ".in";
    string fout = taskname + ".out";
    const char* FIN = fin.c_str();
    const char* FOUT = fout.c_str();
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
}
template<typename T>
void read(vector<T>& v){
    int n=v.size();
    for(int i=0; i<n; i++)
        cin >> v[i];
}
template<typename T>
vector<T>UNQ(vector<T>a){
    vector<T>ans;
    for(T t:a)
        if(ans.empty() || t!=ans.back())
            ans.push_back(t);
    return ans;
}



void solve();
int main(){
    GLHF;
    int t=1;
    //cin >> t;
    while(t--)
        solve();
}

struct Seg{

    int l,r,m,sum=0;
    Seg* lp=0,*rp=0;

    Seg(int l,int r):l(l),r(r),m((l+r)/2){}
    void expand(){
        if(!lp)lp=new Seg(l,m);
        if(!rp)rp=new Seg(m,r);
    }

    void upd(int i,int v=1){
        sum+=v;
        if(l+1==r)return;
        expand();

        if(i<m)
            lp->upd(i,v);
        else
            rp->upd(i,v);
        sum=lp->sum+rp->sum;
    }

    int qur(int a,int b){
        if(r<=a || b<=l)return 0;
        else if(a<=l && r<=b)return sum;
        expand();
        return lp->qur(a,b)+rp->qur(a,b);
    }
};

struct Seg2{
    Seg2 *lp=0,*rp=0;
    Seg* data=0;
    int l,r,m;

    Seg2(int l,int r):l(l),r(r),m((l+r)/2){
        data=new Seg(0,1e9+1);
    }

    void expand(){
        if(!lp)lp=new Seg2(l,m);
        if(!rp)rp=new Seg2(m,r);
    }

    void upd(int i,int j){
        data->upd(j);

        if(l+1==r)return;

        expand();
        if(i<m)lp->upd(i,j);
        else rp->upd(i,j);

        int s=data->qur(j,j+1);
        int ls=lp->data->qur(j,j+1);
        int rs=rp->data->qur(j,j+1);

        data->upd(j,ls+rs-s);
    }

    int qur(int a1,int b1,int a2,int b2){
        if(r<=a1 || l>=b1)return 0;
        else if(a1<=l && r<=b1)
            return data->qur(a2,b2);
        expand();
        return lp->qur(a1,b1,a2,b2)+rp->qur(a1,b1,a2,b2);
    }

};

void solve() {
    int n,q;
    cin >> n >> q;

    vpi a(n);
    read(a);

    sort(all(a),[&](pi p1,pi p2){
        return p1.first+p1.second>p2.first+p2.second;
    });

    vvi queries(q,vi(4));
    for(int i=0; i<q; i++){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
        queries[i][3]=i;
    }
    sort(all(queries),[&](vi v1,vi v2){
        return vi({v1[2],v1[0],v1[1]})>vi({v2[2],v2[0],v2[1]});
    });

    vi ans(q);

    Seg2 ST(0,1e9 +1);
    vpi has;
    for(int i=0,j=0; i<q; i++){
        int x=queries[i][0],y=queries[i][1],z=queries[i][2];
        while(j<n && a[j].first+a[j].second>=z) {
            ST.upd(a[j].first,a[j].second);
            j++;
        }

        int ix=queries[i][3];

        ans[ix]=ST.qur(x,1e9 +1,y,1e9 +1);
    }

    for(int x:ans)cout << x << "\n";
}

Compilation message

examination.cpp: In function 'void usaco(std::string)':
examination.cpp:47:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     freopen(FIN, "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen(FOUT, "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 5 ms 2356 KB Output is correct
5 Correct 3 ms 2380 KB Output is correct
6 Correct 4 ms 2380 KB Output is correct
7 Correct 774 ms 595352 KB Output is correct
8 Correct 699 ms 595248 KB Output is correct
9 Correct 701 ms 595672 KB Output is correct
10 Correct 481 ms 395160 KB Output is correct
11 Correct 582 ms 432056 KB Output is correct
12 Correct 103 ms 808 KB Output is correct
13 Correct 653 ms 595680 KB Output is correct
14 Correct 639 ms 596260 KB Output is correct
15 Correct 691 ms 595876 KB Output is correct
16 Correct 457 ms 374448 KB Output is correct
17 Correct 398 ms 355572 KB Output is correct
18 Correct 89 ms 716 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2915 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 2915 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 844 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 5 ms 2356 KB Output is correct
5 Correct 3 ms 2380 KB Output is correct
6 Correct 4 ms 2380 KB Output is correct
7 Correct 774 ms 595352 KB Output is correct
8 Correct 699 ms 595248 KB Output is correct
9 Correct 701 ms 595672 KB Output is correct
10 Correct 481 ms 395160 KB Output is correct
11 Correct 582 ms 432056 KB Output is correct
12 Correct 103 ms 808 KB Output is correct
13 Correct 653 ms 595680 KB Output is correct
14 Correct 639 ms 596260 KB Output is correct
15 Correct 691 ms 595876 KB Output is correct
16 Correct 457 ms 374448 KB Output is correct
17 Correct 398 ms 355572 KB Output is correct
18 Correct 89 ms 716 KB Output is correct
19 Runtime error 2915 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -