oj.uz

Submission #715175

# Submission time Handle Problem Language Result Execution time Memory
715175 2023-03-26T07:12:57 Z Huseyn123 Examination (JOI19_examination) C++17
20 / 100
 87 ms 10148 KB 
#include <bits/stdc++.h>
#define MAX 200001
#define INF LLONG_MAX
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ins insert
#define ff first
#define ss second
#define gett(x,m) get<m>(x)
#define all(a) a.begin(),a.end()
#define lb(a,b) lower_bound(all(a),b)
#define ub(a,b) upper_bound(all(a),b)
#define sortv(a) sort(all(a))
#define sorta(a,sz) sort(a,a+sz)
#define inputar(a,b){\
    for(int i=0;i<b;i++){\
        cin >> a[i];\
    }\
}
#define inputvec(a,b){\
    for(int i=0;i<b;i++){\
        ll num;\
        cin >> num;\
        a.pb(num);\
    }\
}
#define outputar(a,b){\
    for(int i=0;i<b;i++){\
        cout << a[i] << " ";\
    }\
    cout << "\n";\
}
#define outputvec(a){\
    for(auto x:a){\
        cout << x << " ";\
    }\
    cout << "\n";\
}
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef tuple<ll,ll,ll> tll;
typedef pair<ll,ll> pll;
typedef double db;
typedef long double ldb;
inline void USACO(string filename){
  freopen((filename+".in").c_str(),"r",stdin);
  freopen((filename+".out").c_str(),"w",stdout);
}
ll n,q,t=1,m,n2,m2,k,cnt=0,a[MAX],b[MAX],d2[MAX],x,y,z,x2,y2,z2,res1=0,cnt1,cnt2,cnt3;
struct segtree2{
    int size;
    vector<pll> tree;
    void init(int n){
        size=1;
        while(size<n){
            size*=2;
        }
        tree.assign(2*size,{-1,-1});
    }
    void upd(int cnt,int l,int r,int v,int x,int lx,int rx){
        if(lx>=r || rx<=l){
            return;
        }
        if(lx>=l && rx<=r){
            tree[x]=mp(v,cnt);
            return;
        }
        int m=(lx+rx)/2;
        upd(cnt,l,r,v,2*x+1,lx,m);
        upd(cnt,l,r,v,2*x+2,m,rx);
    }
    void upd(int cnt,int l,int r,int v){
        upd(cnt,l,r,v,0,0,size);
    }
    pll get(int i,int x,int lx,int rx){
        if(rx-lx==1){
            return tree[x];
        }
        int m=(lx+rx)/2;
        pll res;
        if(i<m){
            res=get(i,2*x+1,lx,m);
        }
        else{
            res=get(i,2*x+2,m,rx);
        }
        if(tree[x].ss>res.ss){
            res=tree[x];
        }
        return res;
    }
    ll get(int i){
        return get(i,0,0,size).ff;
    }
};
ll sum[MAX];
void update(ll x,ll v){
    while(x<MAX){
        sum[x]+=v;
        x+=x&-x;
    }
}
ll get_sum(ll x){
    ll res=0;
    while(x>=1){
        res+=sum[x];
        x-=x&-x;
    }
    return res;
}
struct query{
    ll x,y,z,id;
};
bool comp(query a,query b){
    return a.x>b.x;
}
vector<query> queries;
void solve(){
    cin >> n >> m;
    queries.resize(m);
    vector<pll> c;
    for(int i=0;i<n;i++){
        cin >> x >> y;
        x++;
        y++;
        c.pb(mp(x,y));
    }
    for(int i=0;i<m;i++){
        queries[i].id=i;
        cin >> queries[i].x >> queries[i].y >> queries[i].z;
        queries[i].x++;
        queries[i].y++;
        queries[i].z+=2;
    }
    sort(all(queries),comp);
    sortv(c);
    reverse(all(c));
    ll j=0;
    for(int i=0;i<m;i++){
        while(j<n && c[j].ff>=queries[i].x){
            update(c[j].ss,1);
            j++;
        }
        ll h=get_sum(MAX-1)-get_sum(queries[i].y-1);
        b[queries[i].id]=h;
    }
    for(int i=0;i<m;i++){
        cout << b[i] << "\n";
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //USACO("poetry");
    //cin >> t;
    ll cnt1=1;
    while(t--){
        solve();
        cnt1++;
    }
}
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ifstream fin("template.in");
ofstream fout("template.out");
*/
/*
ll b[51][51];
b[0][0] = 1;
    for (int n = 1; n <= 50; ++n){
        b[n][0] = b[n][n] = 1;
        for (int k = 1; k < n; ++k)
            b[n][k] = b[n - 1][k - 1] + b[n - 1][k];
    }
*/

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7220 KB Output is correct
2 Correct 78 ms 9800 KB Output is correct
3 Correct 87 ms 9820 KB Output is correct
4 Correct 66 ms 8224 KB Output is correct
5 Correct 80 ms 8972 KB Output is correct
6 Correct 57 ms 7524 KB Output is correct
7 Correct 75 ms 9752 KB Output is correct
8 Correct 70 ms 9744 KB Output is correct
9 Correct 68 ms 9588 KB Output is correct
10 Correct 58 ms 8836 KB Output is correct
11 Correct 86 ms 8100 KB Output is correct
12 Correct 46 ms 7192 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 7220 KB Output is correct
2 Correct 78 ms 9800 KB Output is correct
3 Correct 87 ms 9820 KB Output is correct
4 Correct 66 ms 8224 KB Output is correct
5 Correct 80 ms 8972 KB Output is correct
6 Correct 57 ms 7524 KB Output is correct
7 Correct 75 ms 9752 KB Output is correct
8 Correct 70 ms 9744 KB Output is correct
9 Correct 68 ms 9588 KB Output is correct
10 Correct 58 ms 8836 KB Output is correct
11 Correct 86 ms 8100 KB Output is correct
12 Correct 46 ms 7192 KB Output is correct
13 Incorrect 78 ms 10148 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -