Yandex qual
全然更新してねえ… 簡単なやつで更新しよう
A.やるだけ
B.やるだけ
C.やるだけ
D.
segtreeをかく→TLE→BITをかく→TLE→ゆるして
Challenge Phase
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define rep1(i,n) for(int i=1;i<=(n);++i) #define all(c) (c).begin(),(c).end() int x[100000],y[100000],bit[100001],p=100000000,n; vector<int> vx,vy; int query(int id){ int mn=p; while(id>0){ mn=min(mn,bit[id]); id-=(id& -id); } return mn; } void update(int id,int x){ while(id<=n){ bit[id]=min(bit[id],x); id+=(id& -id); } } int main(){ scanf("%d",&n); rep(i,n){ scanf("%d%d",&x[i],&y[i]); vx.push_back(x[i]); vy.push_back(y[i]); } sort(all(vx)); sort(all(vy)); vx.erase(unique(all(vx)),vx.end()); vy.erase(unique(all(vy)),vy.end()); rep(i,n){ x[i]=find(all(vx),x[i])-vx.begin(); y[i]=find(all(vy),y[i])-vy.begin(); } rep1(i,n) bit[i]=p; rep(i,n){ if(query(x[i]+1)<=y[i]){ cout << "Invisible paper detected" << endl; return 0; } update(x[i]+1,y[i]); } cout << "Well done" << endl; return 0; }
E.
数列の,連続する部分和の最大を求める
これまで(別に変更がなくても)segtreeを書いていた気がしていて、普通にO(n)でできることに気づいた
左から見ていき、その場所(値a)から左に伸ばした時の最大値(mxlとおく),そこまででの部分和の最大(mx)とおく とすると、mxl=max(0,mxl+a),mx=max(mx,mxl)となる
これまでなんで気づかなかったんだろう
F.
[rem]getline(cin,s)と書けば" "ごと読み込める
s.insert(i,t)でs[0]..s[i-1],t[0]..t[t.size()-1],s[i]...となる
[rem]と書いてあるのは自分用のメモ