oj.uz

Submission #933264

# Submission time Handle Problem Language Result Execution time Memory
933264 2024-02-25T10:50:16 Z yeediot Curtains (NOI23_curtains) C++14
100 / 100
 1037 ms 95196 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define sz(x) (int)(x.size())
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define vi vector<int>
#define vp vector<pii>
#define vvi vector<vi>
#define ykh mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count())
#define __lg(x) 63-__builtin_clzll(x)
#define pow2(x) (1LL<<x)
void __print(int x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef local
void setio(){freopen("/Users/iantsai/Library/Mobile Documents/com~apple~CloudDocs/cpp/Empty.md","r",stdin);}
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
void setio(){}
#define debug(x...)
#endif
void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
struct line{
    int a,b;
    int operator()(const int x)const{
        return a*x+b;
    }
};
bool check(line l1,line l2,line l3){
    return (l3.b-l2.b)*(l1.a-l2.a)<=(l2.b-l1.b)*(l2.a-l3.a);
}
const int mxn=5e5+5;
int seg[4*mxn];
int tag[4*mxn];
#define lc id*2
#define rc id*2+1
void push(int id){
    seg[lc]=max(seg[lc],tag[id]);
    seg[rc]=max(seg[rc],tag[id]);
    tag[lc]=max(tag[lc],tag[id]);
    tag[rc]=max(tag[rc],tag[id]);
    tag[id]=0;
}
void modify(int l,int r,int id,int ql,int qr,int v){
    if(qr<l or r<ql)return;
    if(ql<=l and r<=qr){
        seg[id]=max(seg[id],v);
        tag[id]=max(tag[id],v);
        return;
    }
    int mm=l+r>>1;
    push(id);
    modify(l,mm,id*2,ql,qr,v);
    modify(mm+1,r,id*2+1,ql,qr,v);
    seg[id]=min(seg[id*2],seg[id*2+1]);
}
int query(int l,int r,int id,int ql,int qr){
    if(qr<l or r<ql)return 8e18;
    if(ql<=l and r<=qr){
        return seg[id];
    }
    int mm=l+r>>1;
    push(id);
    return min(query(l,mm,id*2,ql,qr),query(mm+1,r,id*2+1,ql,qr));
}
vector<pii>l[mxn],r[mxn];
signed main(){
    setio();
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,q;
    cin>>n>>m>>q;
    vector<pii>cur,qq;
    for(int i=0;i<m;i++){
        int ll,rr;
        cin>>ll>>rr;
        cur.pb({ll,rr});
        r[rr].pb({i,0});
    }
    for(int i=0;i<q;i++){
        int ll,rr;
        cin>>ll>>rr;
        qq.pb({ll,rr});
        r[rr].pb({i,1});
    }
    vector<bool>ans(q);
    for(int i=1;i<mxn;i++){
        for(auto [j,ty]:r[i]){
            if(ty==0){
                modify(1,n,1,cur[j].F,cur[j].S,cur[j].F);
            }
            else{
                if(query(1,n,1,qq[j].F,qq[j].S)>=qq[j].F)ans[j]=1;
                else ans[j]=0;
            }
        }
    }
    for(auto i:ans){
        if(i)cout<<"YES\n";
        else cout<<"NO\n";
    }
}
 /*
 input:
 
 */

Compilation message

curtains.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:73:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mm=l+r>>1;
      |            ~^~
curtains.cpp: In function 'long long int query(long long int, long long int, long long int, long long int, long long int)':
curtains.cpp:84:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |     int mm=l+r>>1;
      |            ~^~
curtains.cpp: In function 'int main()':
curtains.cpp:110:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  110 |         for(auto [j,ty]:r[i]){
      |                  ^
curtains.cpp: In function 'void setIO(std::string)':
curtains.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
curtains.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25256 KB Output is correct
3 Correct 6 ms 25240 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25228 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25256 KB Output is correct
3 Correct 6 ms 25240 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25228 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 8 ms 25288 KB Output is correct
15 Correct 8 ms 25436 KB Output is correct
16 Correct 8 ms 25512 KB Output is correct
17 Correct 7 ms 25284 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 7 ms 25436 KB Output is correct
20 Correct 7 ms 25540 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25256 KB Output is correct
3 Correct 6 ms 25240 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25228 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 8 ms 25288 KB Output is correct
15 Correct 8 ms 25436 KB Output is correct
16 Correct 8 ms 25512 KB Output is correct
17 Correct 7 ms 25284 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 7 ms 25436 KB Output is correct
20 Correct 7 ms 25540 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct
22 Correct 212 ms 49088 KB Output is correct
23 Correct 196 ms 49832 KB Output is correct
24 Correct 251 ms 54212 KB Output is correct
25 Correct 403 ms 71316 KB Output is correct
26 Correct 182 ms 49460 KB Output is correct
27 Correct 421 ms 71644 KB Output is correct
28 Correct 450 ms 71284 KB Output is correct
29 Correct 187 ms 48052 KB Output is correct
30 Correct 132 ms 49844 KB Output is correct
31 Correct 146 ms 54068 KB Output is correct
32 Correct 363 ms 71000 KB Output is correct
33 Correct 134 ms 50704 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25256 KB Output is correct
2 Correct 7 ms 25180 KB Output is correct
3 Correct 7 ms 25180 KB Output is correct
4 Correct 7 ms 25180 KB Output is correct
5 Correct 9 ms 25272 KB Output is correct
6 Correct 8 ms 25688 KB Output is correct
7 Correct 7 ms 25632 KB Output is correct
8 Correct 131 ms 50360 KB Output is correct
9 Correct 153 ms 54048 KB Output is correct
10 Correct 339 ms 70764 KB Output is correct
11 Correct 130 ms 50416 KB Output is correct
12 Correct 107 ms 37928 KB Output is correct
13 Correct 142 ms 37896 KB Output is correct
14 Correct 86 ms 37824 KB Output is correct
15 Correct 85 ms 37828 KB Output is correct
16 Correct 87 ms 37940 KB Output is correct
17 Correct 100 ms 38060 KB Output is correct
18 Correct 802 ms 88816 KB Output is correct
19 Correct 787 ms 88760 KB Output is correct
20 Correct 633 ms 88496 KB Output is correct
21 Correct 657 ms 88752 KB Output is correct
22 Correct 652 ms 88752 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25256 KB Output is correct
3 Correct 6 ms 25240 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25228 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 8 ms 25288 KB Output is correct
15 Correct 8 ms 25436 KB Output is correct
16 Correct 8 ms 25512 KB Output is correct
17 Correct 7 ms 25284 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 7 ms 25436 KB Output is correct
20 Correct 7 ms 25540 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct
22 Correct 105 ms 35968 KB Output is correct
23 Correct 94 ms 35772 KB Output is correct
24 Correct 147 ms 38016 KB Output is correct
25 Correct 135 ms 37920 KB Output is correct
26 Correct 107 ms 39448 KB Output is correct
27 Correct 120 ms 39476 KB Output is correct
28 Correct 92 ms 35852 KB Output is correct
29 Correct 118 ms 38588 KB Output is correct
30 Correct 140 ms 37820 KB Output is correct
31 Correct 130 ms 38080 KB Output is correct
32 Correct 117 ms 38080 KB Output is correct
33 Correct 138 ms 38460 KB Output is correct
34 Correct 132 ms 38340 KB Output is correct
35 Correct 121 ms 38084 KB Output is correct
36 Correct 130 ms 38416 KB Output is correct
37 Correct 111 ms 37940 KB Output is correct
38 Correct 106 ms 37848 KB Output is correct
39 Correct 97 ms 37972 KB Output is correct
40 Correct 95 ms 38220 KB Output is correct
41 Correct 93 ms 37992 KB Output is correct
42 Correct 90 ms 37864 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25256 KB Output is correct
3 Correct 6 ms 25240 KB Output is correct
4 Correct 6 ms 25180 KB Output is correct
5 Correct 6 ms 25180 KB Output is correct
6 Correct 6 ms 25228 KB Output is correct
7 Correct 6 ms 25180 KB Output is correct
8 Correct 6 ms 25176 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 6 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25180 KB Output is correct
13 Correct 7 ms 25436 KB Output is correct
14 Correct 8 ms 25288 KB Output is correct
15 Correct 8 ms 25436 KB Output is correct
16 Correct 8 ms 25512 KB Output is correct
17 Correct 7 ms 25284 KB Output is correct
18 Correct 7 ms 25436 KB Output is correct
19 Correct 7 ms 25436 KB Output is correct
20 Correct 7 ms 25540 KB Output is correct
21 Correct 7 ms 25436 KB Output is correct
22 Correct 212 ms 49088 KB Output is correct
23 Correct 196 ms 49832 KB Output is correct
24 Correct 251 ms 54212 KB Output is correct
25 Correct 403 ms 71316 KB Output is correct
26 Correct 182 ms 49460 KB Output is correct
27 Correct 421 ms 71644 KB Output is correct
28 Correct 450 ms 71284 KB Output is correct
29 Correct 187 ms 48052 KB Output is correct
30 Correct 132 ms 49844 KB Output is correct
31 Correct 146 ms 54068 KB Output is correct
32 Correct 363 ms 71000 KB Output is correct
33 Correct 134 ms 50704 KB Output is correct
34 Correct 7 ms 25256 KB Output is correct
35 Correct 7 ms 25180 KB Output is correct
36 Correct 7 ms 25180 KB Output is correct
37 Correct 7 ms 25180 KB Output is correct
38 Correct 9 ms 25272 KB Output is correct
39 Correct 8 ms 25688 KB Output is correct
40 Correct 7 ms 25632 KB Output is correct
41 Correct 131 ms 50360 KB Output is correct
42 Correct 153 ms 54048 KB Output is correct
43 Correct 339 ms 70764 KB Output is correct
44 Correct 130 ms 50416 KB Output is correct
45 Correct 107 ms 37928 KB Output is correct
46 Correct 142 ms 37896 KB Output is correct
47 Correct 86 ms 37824 KB Output is correct
48 Correct 85 ms 37828 KB Output is correct
49 Correct 87 ms 37940 KB Output is correct
50 Correct 100 ms 38060 KB Output is correct
51 Correct 802 ms 88816 KB Output is correct
52 Correct 787 ms 88760 KB Output is correct
53 Correct 633 ms 88496 KB Output is correct
54 Correct 657 ms 88752 KB Output is correct
55 Correct 652 ms 88752 KB Output is correct
56 Correct 105 ms 35968 KB Output is correct
57 Correct 94 ms 35772 KB Output is correct
58 Correct 147 ms 38016 KB Output is correct
59 Correct 135 ms 37920 KB Output is correct
60 Correct 107 ms 39448 KB Output is correct
61 Correct 120 ms 39476 KB Output is correct
62 Correct 92 ms 35852 KB Output is correct
63 Correct 118 ms 38588 KB Output is correct
64 Correct 140 ms 37820 KB Output is correct
65 Correct 130 ms 38080 KB Output is correct
66 Correct 117 ms 38080 KB Output is correct
67 Correct 138 ms 38460 KB Output is correct
68 Correct 132 ms 38340 KB Output is correct
69 Correct 121 ms 38084 KB Output is correct
70 Correct 130 ms 38416 KB Output is correct
71 Correct 111 ms 37940 KB Output is correct
72 Correct 106 ms 37848 KB Output is correct
73 Correct 97 ms 37972 KB Output is correct
74 Correct 95 ms 38220 KB Output is correct
75 Correct 93 ms 37992 KB Output is correct
76 Correct 90 ms 37864 KB Output is correct
77 Correct 986 ms 90228 KB Output is correct
78 Correct 954 ms 90452 KB Output is correct
79 Correct 844 ms 95152 KB Output is correct
80 Correct 872 ms 95196 KB Output is correct
81 Correct 817 ms 92440 KB Output is correct
82 Correct 851 ms 94064 KB Output is correct
83 Correct 1037 ms 90136 KB Output is correct
84 Correct 938 ms 90780 KB Output is correct
85 Correct 892 ms 91184 KB Output is correct
86 Correct 860 ms 89212 KB Output is correct
87 Correct 825 ms 89260 KB Output is correct
88 Correct 861 ms 93616 KB Output is correct