제출 #398984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398984		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	0 / 100	2921 ms	136400 KiB

sortbooks

#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 1000001;

struct resp{
    int l, r, v, segpos;
};
struct queries{
    int l, r, limit, v;
};

int tree[4*MAXN];

void update(int id, int l, int r, int q, int val){
    if(l > q || r < q)
        return;
    if(l == q && r == q){
        tree[id] = val;
        return;
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    update(e,l,m,q,val);
    update(d,m+1,r,q,val);
    tree[id] = max(tree[e],tree[d]);
}

int query(int id, int l, int r, int ql, int qr){
    if(l > qr || r < ql)
        return 0;
    if(ql<=l && r <= qr){

        return tree[id];
    }
    int e = id*2+1;
    int d = id*2+2;
    int m = (l+r)>>1;
    return max(query(e,l,m,ql,qr), query(d,m+1,r,ql,qr));
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    vector<queries> q(m);
    for(int i = 0; i < n; i++) 
        cin >> v[i];
    for(int i = 0; i < m; i++)
        cin >> q[i].l >> q[i].r >> q[i].limit, q[i].l--, q[i].r--;

    vector<int> order(n), orderq(m);
    iota(order.begin(), order.end(), 0); 
    iota(orderq.begin(), orderq.end(), 0); 
    sort(order.begin(),order.end(), [&](int a, int b){
        if(v[a] == v[b])
            return a < b;
        return v[a] > v[b];
    });
    sort(orderq.begin(),orderq.end(), [&](int a, int b){
        return q[a].r < q[b].r;
    });
    set<int> s;
    vector<resp> v2;
    for(int i = 0; i < n; i++){
        auto aux = s.insert(order[i]);
        if(aux.first!=s.begin()){
            aux.ff--;
            v2.push_back({*aux.ff, order[i], v[*aux.ff] + v[order[i]]});
        }
    }
    sort(v2.begin(),v2.end(),[](resp a, resp b){return a.r < b.r;});

    vector<int> orderl (v2.size());

    iota(orderl.begin(),orderl.end(),0);
    sort(orderl.begin(),orderl.end(),[&](int a, int b){return v2[a].l < v2[b].l;});

    for(int i = 0; i < v2.size(); i++)
        v2[orderl[i]].segpos = i;
    
    int ptr = 0;
    for(int i = 0; i < m; i++){
        queries &cur = q[orderq[i]];
        while(ptr<v2.size() && v2[ptr].r <= cur.r){
            update(0,0,v2.size()-1,v2[ptr].segpos,v2[ptr].v);
            ptr++;
        }

        cur.v = (query(0,0,v2.size()-1, cur.l, cur.r) <= cur.limit);
    }
    for(queries i : q)
        cout << i.v << '\n';
    return 0;

}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:92:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<resp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i = 0; i < v2.size(); i++)
      |                    ~~^~~~~~~~~~~
sortbooks.cpp:98:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<resp>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         while(ptr<v2.size() && v2[ptr].r <= cur.r){
      |               ~~~^~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23